Методическое пособие по логическому программированию

Название “Пролог” есть сокращение для "ПРОграммирование в терминах ЛОГики". Пролог может быть использован в различных приложениях, относящихся к искусственному интеллекту:

– общение с ЭВМ на естественном языке;

– символьные вычисления;

– написание компиляторов;

– базы данных;

– экспертные системы и т.д.

Диалект Пролога язык PDC Prolog является компиляторно-ориентированным языком программирования высокого уровня, разработан фирмой и предназначен для программирования задач из области искусственного интеллекта.

Следует отметить некоторую трудность усвоения языка начинающими пользователями. Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Как следствие, в языке отсутствуют управляющие конструкции типа if … then, while … do; нет даже оператора присваивания. Программа, составленная на этом языке, не содержит детального описания последовательности шагов, ведущих к результату. Однако методические трудности, связанные с обучением использованию Пролога начинающих программистов, можно успешно преодолеть на основе принципа – "делай как мы".

1. Организация вычислительного процесса

Программа на Прологе включает набор процедур, каждая из которых представляет собой определенный предикат. Предикат имеет общую форму:

А:– В1, В2, ... , Вn,

которая интерпретируется : "А является истинным, если В1, В2, ...., Вn являются истинными". Если n=0, то такое предложение выражает факт, и это записывается "А." .

Если получен запрос (т.е. цель, которую нужно удовлетворить), Пролог пытается определить его истинность двумя способами. Во-первых, цель успешно удовлетворяется (т.е. считается истинной), если она сопоставляется с существующим фактом (так как факты всегда являются истинными). Во-вторых, цель считается истинной, если она сопоставляется с заголовком “А” правила " А, если В1, ... , Вn " и если подцели В1, ... , Вn могут быть завершены успешно. В случае успешного сопоставления Пролог выдает ответ "yes", т.е. цель согласована.

Если попытка сопоставить подцель с фактами в базе знаний завершается неудачей и остаются альтернативные (еще не применявшиеся правила или факты), Пролог будет осуществлять возврат и использовать эти альтернативы. Если все альтернативы закончились неудачно, то считается, что начальная цель неудовлетворительна. В этом случае выдается ответ "no".

В качестве аргументов цель может содержать константы или переменные. Переменная представляет собой неконкретизированную величину, которую Пролог должен конкретизировать, т.е. выполнить ее подстановку константой. После того, как цель, содержащая переменные, будет согласована, Пролог выдаст значения, которыми будут заменены переменные, входящие в цель.

В Прологе нет оператора присваивания, а есть логическое сравнение, обозначаемое знаком равенства, поэтому понятно, что запись вида N = N+ 1 бессмысленна: величина никогда не равна самой себе, увеличенной на единицу, надо использовать другую переменную: N1 = N + 1.

В Прологе отсутствуют глобальные переменные, т.е. одни и те же имена переменных можно употреблять во многих правилах данной программы, при этом между такими переменными будет отсутствовать какая-либо связь.

В синтаксисе Пролога факт имеет следующий вид:

relation(object, object,.....object).

Правила имеют основную форму:

relation(object, object,.....object) :–

relation1(object, object,.....object) ,

...

relationN(object, object,.....object).

Правило Пролога можно представить как небольшую процедуру с локальными переменными. Основное отличие такой процедуры от процедуры, написанной на Паскале: предикат может выполнять несколько функций, в зависимости от состояния аргументов (конкретизированы они или нет), при этом каждому такому состоянию аргументов соответствует своя статья предиката.

Система Пролог обладает встроенным механизмом логического вывода, благодаря чему от пользователя требуется только описание своей задачи с помощью аппарата логики предикатов первого порядка, а поиск решения система берет на себя. Рассмотрим простую программу на Прологе:

p :– q,s.

p :– r,t.

Эту программу можно прочитать следующим образом. При выполнении процедуры p выполняются процедуры q и s. Если они завершаются успешно, то и процедура p считается успешно завершенной. Если это не так, то выполняются процедуры r и t. В этом случае процедура успешно завершается, если r и t завершены успешно. В противном случае процедура p терпит неудачу. Этот процесс возврата к поиску других решений называется бэктрекингом (backtracking).

Основным механизмом поиска решения задачи в Прологе является сопоставление, и он позволяет решать широкий класс задач наиболее простым способом: путем перебора всех возможных состояний. Однако в ряде случаев требуется управлять этим процессом и реализовывать другие стратегии вывода, встраивая их в режим естественного обратного вывода Пролога. Несмотря на то, что в Прологе отсутствуют традиционные управляющие конструкции типа оператора перехода, условного оператора, оператора цикла, язык логического программирования позволяет создавать такие механизмы своими методами.

Наиболее простой способ управлять процессом вычисления – располагать предложения в том или ином порядке, что в терминологии алгоритмов соответствует последовательному вычислительному процессу. Реализация разветвляющегося процесса также осуществляется довольно просто: каждой ветви вычислений соответствует отдельная статья предиката. Турбо-Пролог также прекрасно приспособлен для организации циклов. Основные механизмы реализации процесса повторений – использование рекурсии и механизма бэктрекинга. Примеры возможных способов реализации алгоритмов рассмотрены ниже.

2. Основные элементы языка

2.1. Имена

Имена используются для обозначения переменных, символьных констант, объявлений типов и предикатов.

Имя может начинаться с любой латинской буквы или символа подчеркивания "_", затем следует любая комбинация букв, цифр и символа "_".

При образовании имен необходимо учитывать следующие правила:

- имена строковых констант должны начинаться с маленькой буквы;

- имена переменных должны начинаться с большой буквы или символа подчеркивания "_".

2.2. Типы данных

Имеется следующие стандартные типы данных:

symbol	Символьная строка, которая начинается со строчной буквы или заключена в кавычки
string	Также символьная строка, но имеющая другое внутреннее представление
char	Отдельный символ, заключенный в апострофы
integer	Целое число в диапазоне от -32768 до 32767
real	Любое вещественное число

2.3. Константы и переменные

Константы Пролога должны быть записаны:

а) либо с маленькой буквы (исключая кириллицу):

fact1, summa, person ;

б) либо стоять в одинарных кавычках (отдельный символ) или бинарных кавычках (строковая константа):

'c' , "summa=", "сумма" ;

в) либо они являются числами, целыми или вещественными:

25, 0.5, 3.2e-4 .

Таким образом, константы могут быть любого из стандартных типов Пролога. В программе тип констант явно не указывается.

Переменные – это цепочки, состоящие из букв, цифр и символа подчеркивания. Имя переменной всегда начинается с прописной буквы или с символа подчеркивания:

X, Summa, List_of_members, _x23.

Переменная может иметь один из стандартных типов, или тип ее определяется в секции описания областей определения (типов) domaims. Можно также использовать так называемую анонимную переменную, которая записывается в виде одного символа подчеркивания.

2.4. Программные секции Пролога

Программа на Прологе состоит из нескольких программных секций, каждой из которых предшествует ключевое слово, представленное в следующей таблице:

Domains	Определение типов данных
Database	Объявление предикатов базы данных
Predicates	Объявление предикатов
Clauses	Определение фактов или правил
Goal	Цель

В программе необязательно наличие всех секций. Обычно в небольшой программе бывают разделы Predicates и Clauses.

В программе может использоваться только одна цель; если цель не указана, Пролог цель запросит. Обычно цель записывают в конце программы.

Ключевые слова разделов можно записывать прописными и строчными буквами.

Комментарии к программе записываются либо парами символов слэш-звездочка:

/* это комментарий,

он занимает несколько строк */

либо остаток строки записывается после знака процента:

% это тоже комментарий

2.4.1. Секция Domains

Для объявления секции domains используются следующие форматы:

1. Первый формат:

name = t ,

где name – имя Пролога, t – один из стандартных типов. Это объявление используется для объектов, которые синтаксически схожи, а семантически различны. Например, предложение

age, number = integer

объявляет два domains целого типа.

2. Второй формат:

mylist = elevent* ,

где mylist – объявление списка элементов, element – элемент, ранее описанный пользователем в Domains либо один из стандартных типов Турбо-Пролога, “*” обозначает список. Hапример,

namlist = integer*

объявляет список целых чисел.

3. Третий формат описывает сложную область определения, задает описание структур.

region = functor1(d1,d2,...); functor2(d3,d4,...);...

где region объявляет сложную область, functor1,functor2 – имена альтернатив составной области, d1,d1,...,d3,d4 – один из типов Пролога, стандартный или определенный ранее в программе в Domains (описание типов может отсутствовать).

Пример:

object = int(integer); str(string)

mesto = sprava; sleva .

Данный способ указания Domains позволяет также рекурсивно описывать объекты сложных типов (деревьев).

2.4.2. Секция Ppredicates

Здесь указываются все имена предикатов с соответствующими областями определения аргументов. Аргументы дизъюнктов Пролога называются термами. Существует три типа термов: константа, переменная, составной терм (структура).

Общий вид описания предиката:

name(d1,d2,...) ,

где name – имя предиката, d1, d2,... – соответственно области определения аргумента1, аргумента2 и т.д. Например:

syn(string)

math(preson,person) .

2.4.3. Секция Database

Объявление оперативной базы данных. Синтаксис объявления такой же, как и в секции Predicates. Объявленные здесь предикаты не должны объявляться в секции Predicates, но дизъюнкты этих предикатов могут присутствовать в секции Clauses.

2.4.4. Секция Clauses

Здесь описываются все дизъюнкты всех предикатов. Другое название дизъюнктов – статьи, предложения или клозы. Это факты и правила, соответствующие каждому из объявленных предикатов. Такой дизъюнкт имеет следующий синтаксис:

functor(d1,d2,...) :– cond1, cond2,... .

Здесь functor – имя предиката;

functor(d1,d2,...) – голова дизъюнкта;

cond1,cond2,... – условия истинности дизъюнкта;

":–" -обозначение "ЕСЛИ".

Если опущены условия, то functor(d1,d2,...) описывает факт. Каждый из дизъюнктов одного предиката секции Clauses соответствует альтернативам этого предиката.

2.4.5. Секция Goal

Здесь указывается вопрос (цель), на который должен ответить Пролог. Записывается он как дизъюнкт без головы и знака ":–" .

3. Примеры программ

3.1. Программы с фактами и простыми правилами

1. Некоторое множество фактов и правил, задающих объекты и отношения между ними, и образуют простую программу на Прологе. Следующие факты

likes(ellen,tennis).

likes(john,football).

likes(tom,baseball).

likes(eric,swimming).

likes(mark,tennis).

соответствуют утверждениям на английском языке:

Ellen likes tennis.

John likes football.

Tom likes baseball.

Eric likes awimming.

Mark likes tennis.

Подобным образом вопрос: "Что любит Джон?" сводится к поиску объекта, который отношение likes (нравится) связывает с Джоном; этот объект и будет служить ответом на запрос. Отметим, что при определении отношения между объектами существенен порядок, в котором эти объекты входят в отношение:

likes(john,football) отличается от likes(football,john).

Запишем эти факты в виде Пролог-программы.

Predicates

likes(string,string)

Clauses

likes(ellen,tennis).

likes(john,football).

likes(tom,baseball).

likes(eric,swimming).

likes(mark,tennis).

После исправления ошибок в программе выберите опцию RUN в меню Пролога. В этой программе цель не указана (отсутствует секция goal, которая, вообще говоря, не обязательна), поэтому когда система в отдельном диалоговом окне запросит цель, введите запрос:

Goal: likes(john,football).

Пролог ответит

Yes

Поскольку такой факт имеется.

2. Построение базы данных. На Прологе чрезвычайно просто организовать реляционную базу данных в виде набора некоторых фактов. Пусть база данных содержит следующие сведения об автомобилях: марка машины, год выпуска, цвет, цена:

car(volvo, 1990, red, 1800).

car(toyota, 1988, black, 2000).

car(ford, 1994, white, 3000).

Наберите эту программу согласно правилам оформления Пролог-программы и исполните команду RUN. Когда система запросит цель, введите запрос:

Goal: car(toyota,_,_,_).

Пролог ответит

1 solution

Yes

в диалоговом окне и будет ждать, когда вы введете другую цель.

В этом запросе использовались анонимные переменные, обозначенные символом подчеркивания. Анонимная переменная используется для обозначения аргументов, значения которых в данный момент могут быть произвольны. Если анонимная переменная встречается в запросе, то ее значение не выводится при ответе системы на этот запрос. Анонимная переменная может также использоваться в записи предикатов, если в предложении она встречается один раз. Примеры записи таких предикатов встретим дальше.

Если зададите в качестве цели

Goal: car(mersedes,1990,_,_) ,

система ответит

No solution ,

поскольку наша база данных не содержит такого утверждения.

Теперь предположим, что мы хотим узнать все марки машин, имеющиеся в базе данных, т.е. задать вопрос: "Каковы те объекты Х, которые являются марками машины?". Тогда наш вопрос запишется так:

Goal: car(Х,_,_,_).

Пролог ответит:

Х=“volvo”

Х="toyota"

Х="ford"

3 solutions.

Можно также задавать вопросы более общего характера. К примеру, если требуется найти все машины, выпущенные до 1992 года, то следует задать запрос, который представляет конъюнкцию целей:

Goal car(X,Y,_,_), Y<1992.

Подобная база данных имеет вид целостных информационных объектов. Более гибким является представление базы данных в виде бинарных отношений, в которых один из атрибутов должен выступать в роли ключа, объединяющего все остальные свойства. Пусть в нашем примере это будет марка машины:

year(volvo, 1990).

year(toyota, 1988).

year(ford, 1994).

color(volvo, red).

color(toyota, black).

color(ford, white).

cost(volvo, 2000).

cost(toyota, 2500).

cosr(ford, 3000).

В случае необходимости атрибуты можно собрать в единое целое при помощи правила:

car(M,Y,C,P) :– year(M,Y), color(M,C), cost(M,P).

3. Использование бэктрекинга (возврата) для получения всех решений. В данном примере предикат-факт counry содержит сведения о названии страны и населении. Программа выдает список стран, население которых превышает 1е7.

Predicates

country(symbol,real)

print_countries

Clauses

country(england,3e7).

country(france,2.3e7).

country(germany,1.6e7).

country(denmark,2.4e6).

country(canada,7.3e6).

country(chile,2.5e).

print_countries :-

country(X,P), % рассматривается очередной факт

P > 1e7,

write(X), % вывод на экран названия страны

nl, % перевод строки

fail. % fail – встроенный предикат, означает «ложь»

print_countries.

Goal print_countries.

После того, как выведен на экран очередной результат, стандартный предикат fail завершает работу предиката print_countries ложно и побуждает Пролог к поиску других решений. Когда будут найдены все решения, второй клоз предиката print_countries позволит программе завершиться истинно.

4. Программа решение квадратного уравнения – типичный пример реализации на Прологе разветвляющегося алгоритма.

predicates

solve(real, real, real) % Запуск программы

reply(real, real, real) % Ветви вычислений

mysqrt(real, real, real) % Вычисление квадратного корня

equal(real, real) % Проверка на равенство

clauses

solve(A, B, C) :– D = B*B-4*A*C, % вычисление дискриминанта

reply(A, B, D), nl.

reply(_, _, D) :– D < 0, write("No solution"), !.

reply(A, B, D) :– D = 0, X=-B/(2*A), write("x=", X), !.

reply(A, B, D) :–

sqrt(D, D, SqrtD),

X1 = (-B + SqrtD)/(2*A),

X2 = (-B – SqrtD)/(2*A),

write("x1 = ", X1," and x2 = ", X2).

Goal solve(3,4,5).

5. Логический вывод. Имеется следующая задача из психологического практикума.

Бутси – коричневая кошка. Корни – черная кошка. Мак – рыжая кошка. Флэш, Ровер, Спот – собаки, Ровер – рыжая, а Спот – белая. Все животные, которыми владеют Том и Кейт, имеют родословные. Том владеет всеми черными и коричневыми животными, а Кейт владеет всеми собаками небелого цвета, которые не являются собственностью Тома. Алан владеет Мак, если Кейт не владеет Бутси и если Спот не имеет родословной. Флэш – пятнистая собака. Определить, какие животные не имеют хозяев. (Ответ: Спот).

Predicates

cat(string)

dog(string)

color(string,string)

have(string,string)

rod(string)

animal(string)

clauses

cat(butsi). cat(korni). cat(mac).

dog(rover). dog(fles). dog(spot).

color(butsi,brown).

color(korni,black).

color(mac,yellow).

color(rover,yellow).

color(spot,white).

color(fles,black_and_white).

have(tom,X):–color(X,black); color(X,brown).

have(keit,X):–dog(X), not(color(X,white)), not(have(tom,X)).

have(alan,mac):–not(have(keit,butsi)), not(rod(spot)).

rod(X):–animal(X), have(tom,X).

rod(X):–animal(X), have(keit,X).

animal(X):–cat(X); dog(X).

goal animal(X),not(have(_,X)),write(X).

3.2. Рекурсии

В Прологе заложено мощное средство, позволяющее определять некоторые отношения, используя эти же отношения, и называемое рекурсией. Подробнее, правило является рекурсивным, если оно вызывает само себя в виде подцели, содержащейся в теле по крайней мере одного из ее утверждений.

6. Примером рекурсивных вычислений является известный алгоритм вычисления факториала. Hа Прологе эта программа может иметь такой вид:

Domains

N, F=real

Predicates

factorial(N,F)

Clauses

factorial(1,1). % база рекурсии, ограничение вычислений

factorial(N,R):– N>0, N1=N-1,

factorial(N1,R1), R=R1*N.

Goal

factorial(8,F),write(F).

При каждом вызове дизъюнкта factorial генерируются новые переменные, которые действуют всегда только на своем уровне вложенности, пока не встретится условие прекращения вычислений. Только после этого на обратном пути прохождения рекурсии определяются результаты, которые передаются вверх.

Любое рекурсивное определение содержит по крайней мере одно нерекурсивное правило и одно или несколько правил с рекурсией. В большинстве случаев имеется по одному правилу каждого типа. Считается, что используется хвостовая рекурсия, если последнее условие в последнем правиле является рекурсивным. Такая рекурсия имеет преимущество перед нехвостовой рекурсией, так как позволяет ограничить рост стека и строго контролировать процесс возврата. Это происходит благодаря очистке стека после успешного сопоставления условия, содержащего рекурсию.

3.3. Программирование циклов

На языке Пролог могут быть реализованы различные алгоритмические методы, позволяющие добиться того же эффекта, что и итеративные циклы в процедурных языках. Выбор алгоритма зависит от того, как представлены данные, которые требуется обрабатывать. Если данные представлены в виде списка (или рекурсивной структуры иного вида), то оптимальным является применение рекурсивного алгоритма. Если же имеется информация в виде базы данных, содержащей факты, то потребуется использовать алгоритм поиска с возвратом (бэктрекинг). И тот, и другой тип цикла можно реализовать с заданным числом повторений или потенциально бесконечным.

7. Рекурсивный цикл со счетчиком. Цикл выполнится 10 раз.

for(10).

for(N):– N<10,

prosess,

N1=N+1,

for(N1).

Goal for(0).

8. Бесконечный рекурсивный цикл. Выполняется ввод и печать символов. Процесс повторяется до нажатия клавиши ENTER, имеющей кодовое число 13.

typewr('\13').

typewr(Char):–write(Char),

readchar(C),

typewr(C).

Goal readchar(Char), typewr(Char).

9. Использование бэктрекинга для перебора всех вариантов. Пусть есть фрагмент программы

fact(f1).

fact(f2).

fact(f3).

print_fact:– fact(X), write(X), fail.

print_fact.

Наличие второго клоза предиката print_fact позволяет всей программе завершиться успешно после печати всех фактов.

10. Большую группу примеров циклов можно продемонстрировать с использованием предиката repeat. Этот предикат программируется следующим образом:

repeat.

repeat:–repeat.

Repeat – это цель, которая всегда успешна. Она недетерминирована, это означает: что всякий раз, когда до нее доходит перебор, порождается новая ветвь вычислений.

Пример цикла с сочетанием repeat и fail.

run:– repeat,

readln(X),

prosess(X,Y),

write(Y),

fail.

Предикат fail заставляет систему осуществлять возврат к repeat и prosess в случае успешного завершения.

Можно также использовать сочетание repeat и стандартного предиката keypressed (вместо repeat – fail) или сочетание not(keypressed) и рекурсии:

run:– repeat, prosess,

keypråssed.

run:– not(keypressed),

prosess, run.

С использованием предиката repeat можно также организовать любое подходящее условие окончания работы цикла:

run:– repeat,

prosess,

write("Будет еще ввод? (y/n)" ),

readchar(Ans), Ans = 'n'.

3.4. Работа со списками

Списки являются одной из основных структур данных Пролога. Список является в некотором смысле аналогом массива в алгоритмических языках программирования. Однако здесь есть существенные отличия. Основным механизмом работы со списками является рекурсия, позволяющая компактно описывать алгоритмы. Для рекурсии не требуется знания точного числа элементов списка, достаточно определения, как правило, головного элемента списка и условия окончания работы рекурсии. Поэтому элементы списков не индексируются, соответственно, количество элементов списка не фиксируется.

Можно также провести аналогию списков Пролога и динамических однонаправленных списковых структур языка Паскаль. От последних их выгодно отличает отсутствие необходимости работать с адресной частью списков.

Для удобства обработки списков в Прологе введены два понятия: голова и хвост. Первый элемент списка (или несколько первых элементов) являются головой списка, а оставшиеся – его хвостом. Тогда список – это структура данных, определяемая следующим образом:

– список является либо пустым,

– либо состоящим из головы и хвоста; головой списка может быть элемент любого типа, а хвост должен быть, в свою очередь, списком.

Для обозначения списка используются квадратные скобки, а для отделения головы списка от его хвоста – символ "|". Например, для списка [1|2,3] элемент 1 является головой, а список [2, 3] хвостом. Пустой список обозначается [ ]. Если список не разделяется на голову и хвост, квадратные скобки можно опустить.

Рассмотрим некоторые предикаты для обработки списков.

11. Добавление элемента в список. Этот предикат должен иметь три аргумента: добавляемый элемент, список и результирующий список. Наиболее простой способ добавить элемент в список – это вставить его в самое начало так, чтобы он стал новой головой. Если X – это новый элемент, который добавляют в список L, то предикат добавления элемента в список можно записать таким образом:

add(X,L, [X|L]).

12. Удаление элемента. Удаление элемента X из списка L можно определить в виде отношения

away(X,L,L1),

где L1 – это список L, из которого удален элемент X.

Отношение away можно определить следующим рекурсивным образом: если X является головой списка, тогда результатом удаления будет хвост этого списка. Если X находится в хвосте списка, тогда его нужно оттуда удалить:

away(X, [X|T],T).

away(X, [Y|T], [Y|T1]):– away(X,T,T1).

13. Проверка принадлежности элемента списку. Требуется определить предикат:

member(X,L).

Здесь L – некоторый список, Х – объект того же типа, что и элементы списка L. Составление предиката может быть основано на следующих соображениях: X есть либо голова списка L, либо X принадлежит хвосту. Это может быть записано в виде двух предложений, первое из которых есть простой факт, ограничивающий вычисления, а второй – рекурсивное правило:

member(X, [X| _ ]).

member(X, [ _ | T ]):– member(X,T).

Напомним, что знаком подчерка здесь обозначена анонимная переменная, значение которой в данном предложении неважно.

Если окажется пустой список, тогда предикат завершается ложно, так как для пустого списка нет своего правила.

14. Сцепление (конкатенация) списков.

conc(L1,L2,L3).

Объединяемые списки задаются первыми двумя аргументами L1 и L2. Список L3 представляет собой конкатенацию этих списков.

Для определения отношения конкатенация отделим два случая:

(1) Если первый список пуст, то второй и третий представляют собой один и тот же список:

ñonc([ ],L,L).

(2) Если первый аргумент не пуст, то он имеет голову и хвост, т.е. [X|L1]. Его сцепление со списком L2 – список [X|L3], где список L3 получен после сцепления списков L1 и L2, т.е.

conc([X|L1],L2,[X|L3]):–conc(L1,L2,L3).

15. Удаление из списка повторяющихся элементов. Аргументами предиката unik являются два списка: исходный и результирующий. Смысл алгоритма прост: если элемент присутствует в списке (проверяется предикатом member), то он не записывается в результирующий список, иначе добавляется в качестве головного элемента.

unik([ ],[ ]).

unik([H|T], L):– member(H,T), unik(T,L).

unik([H|T], [H|L]):– unik(T,L).

16. Обращение списка. Определим предикат

reverse(L1,L2).

Аргументы L1 и L2 – два списка, из которых список L2 содержит элементы списка L1, записанные в обратном порядке.

reverse(L1,L2):–reverse1(L1,[],L2).

reverse1([],L,L).

reverse1([H|T],L1,L2):–reverse1(T,[H|L1],L2).

Предикат reverse в данном случае является интерфейсным, он запускает в работу основной рабочий предикат reverse1, имеющий дополнительный второй аргумент – список, который вначале пуст, и используется собственно для обращения списка. На каждом шаге рекурсии один элемент исходного списка становится головой промежуточного списка. Третий аргумент передается от шага к шагу и конкретизируется в момент достижения базового состояния предиката reverse1. Когда первый список исчерпан, второй уже содержит элементы, записанные в обратном порядке. Отметим, что наличие третьего аргумента, фиксирующего результат, обязательно, т.к. после обратного прохождения рекурсии все конкретизированные переменные принимают свои первоначальные значения.

17. Вычисление суммы элементов списка. Можно выполнить предикатом

sum(L,S).

Здесь S – сумма элементов списка L. Запрограммировать этот предикат можно двумя способами. Рассмотрим сначала более очевидный:

sum([ ],0).

sum([H|T], S1):– sum(T,S2),S1=S2+H.

Декларативный смысл этого алгоритма: если список пуст, то сумма его элементов равна нулю, иначе список можно разделить на голову H и хвост T; сумма элементов такого списка S1, при этом сумма элементов хвоста T есть S2 и S1=S2+H. Обратим внимание, что это рекурсия нехвостовая: в рекурсивном правиле предиката sum рекурсивное условие записано не последним. Нехвостовая рекурсия при последовательных вызовах генерирует промежуточные переменные, которые конкретизируются при обратном прохождении рекурсии.

Рассмотрим работу этого предиката на примере. Пусть требуется найти сумму элементов списка [3,6,1]. Последовательность вызовов следующая:

sum([3|6,1],S) вызывает предикат sum([6,1],S1) и S=S1+3

sum([6|1],S1) вызывает предикат sum([1],S11) и S1=S11+6.

sum([1],S11) вызывает предикат sum([],S111) и S11=S111+1.

sum([ ],S111) удовлетворяется, если S111 конкретизируется 0.

sum([1],S11) удовлетворяется, если S11 конкретизируется 1.

sum([6,1],S1) удовлетворяется, если S1 конкретизируется 7.

sum([3,6,1],S) удовлетворяется, если S конкретизируется 10.

Другой алгоритм вычисления суммы не так нагляден, но он позволяет отменить нехвостовую рекурсию.

sum(L,S):–sum1(L,0,S).

sum1([ ],S,S). % базовое правило, список пуст, сумма накоплена

sum1([H|T],S1,S):–

S2=S1+H,

sum1(T,S2,S).

Здесь используем тот же прием, что и в предикате обращения списка: используем более общий предикат sum1, имеющий дополнительный аргумент S, в котором зафиксируется результат. Декларативный смысл базового правила: если список исчерпан, то сумма накоплена, при этом конкретизируется третий аргумент.

Тот же пример:

sum1([3|6,1], 0, S) вызывает предикат sum1([6,1], 3, S).

sum1([6|1], 3, S) вызывает предикат sum1([1], 9, S).

sum1([1],9, S) вызывает предикат sum1([], 10, S).

sum([ ], 10, S) удовлетворяется, если S конкретизируется 10.

Последовательность возвратов следующая:

sum1([1], 9,1 0)

sum1([6,1], 3,1 0)

sum1([3,6,1], 0, 10)

18. Нахождение максимального элемента списка Здесь нам понадобится вспомогательный предикат max, выбирающий максимальное значение из двух элементов:

max(X,Y,X):– X>=Y.

max(X,Y,Y):– X<Y.

Результативный предикат maxlist(LIST,MAX), где MAX – наибольший элемент списка LIST, выглядит следующим образом:

maxlist([X],X).

maxlist([X,Y|TAIL],MAX):–

maxlist([Y|TAIL],MAXTAIL),

max(X,MAXTAIL,MAX).

Смысл базового правила: максимальный элемент одноэлементного списка равен самому этому элементу. Иначе, если в списке есть хотя бы два элемента X и Y, выбирается максимальный элемент хвоста MAXTAIL и при этом MAX равен наибольшему из X и MAXTAIL. Рекурсия здесь нехвостовая, чтобы обеспечить конкретизацию переменных X и MAXTAIL.

3.5. Нахождение пути на графе

19. Поиск пути на графе – классическая задача. На Прологе она записывается очень компактно. После несложного расширения эта программа сможет отвечать на следующие вопросы:

- как добраться из одной вершины в другую, не посещая дважды одной и той же вершины;

- как пройти по маршруту, посетив заданную вершину;

- как добраться до нужной вершины, избежав некоторых вершин.

Центральной частью программы будет база данных, содержащая данные о сети дуг между вершинами. Эта информация представлена в виде двухаргументного отношения road, например:

road(v1,v3).

road(v4,v1).

road(v3,v5).

Необходимо иметь информацию об обратных направлениях. Чтобы не дублировать базу данных, воспользуемся вспомогательным предикатом road1:

road1(T1,T2):–road(T1,T2);

road(T2,T1).

Для решения этой задачи удобнее всего собирать в список все пройденные вершины пути, исходя из следующих соображений: если существует дуга из вершины X в вершину Y, то путь найден (базовое правило), иначе чтобы найти путь из X в Y, надо найти дугу из X в Z и затем путь из Z в Y (рекурсивное правило):

way(X,Y,[ ]):–road1(X,Y).

way(X,Y,[Z|W]):–road1(X,Z), way(Z,Y,W).

Очевиден недостаток такой записи: система не смущаясь будет находить маршруты, многократно проходящие через одну и ту же вершину. Чтобы избежать этого, следует добавить проверку непринадлежности очередной вершины найденному списку вершин:

way(X,Y,[Z|W]]);- road1(X,Z), way(Z,Y,W), not(membr(Z,W)).

Здесь member – знакомый предикат проверки принадлежности элемента списку.

Рекурсия неизбежно становится нехвостовой, поскольку для предиката member необходимо иметь конкретизированную величину списка W (а список этот конкретизируется только при обратном прохождении рекурсии). Но в такой рекурсии есть опасность зацикливания: можно без конца совершать переходы из одной вершины в другую и обратно, т.к. до проверки непринадлежности вершины маршруту вычисления просто не доходят. Очевидна необходимость хвостовой рекурсии. Можно перейти к такой рекурсии, если начать вычисления от конкретизированного списка (например, пустого) и иметь уже тем больший список, чем больше вложенность рекурсии, т.е. накапливать список в правой части правила. Но в таком случае накопленный список надо зафиксировать в базовом правиле введением дополнительного аргумента:

way(X,Y,W,W):–road1(X,Y).

way(X,Y,W,L):– road1(X,Z), not(member(Z,W)),

way(Z,Y,[Z|W],L).

Для запуска этой программы можно воспользоваться интерфейсным предикатом go, аргументы которого содержат начальный и конечный пункты:

go(Here,There):– way(Here,There,[Here],W),

add(There,W,W1), reverse(W1,W2), write(W2).

Здесь исходный список маршрута конкретизируется начальной вершиной. К списку найденного маршрута добавляется конечный пункт (предикат add). Предикат reverse выполняет инверсию этого списка. Клозы этих последних предикатов было записано ранее.

3.6. Использование структур

Структуры данных являются мощным средством программирования в Прологе. Они позволяют организовать различные фрагменты информации в единые логические единицы, что дает возможность использовать информацию, не думая о деталях ее действительного представления. Широкое применение структур – это также средство представления структурных объектов (баз данных) и управления ими. Использование структур делает Пролог и естественным языком запросов к базе данных.

Структура данных в Прологе задается на составной области определения (третий способ указания Domains).

Рассмотрим ряд примеров с использованием структур.

20. База данных "Семья". Каждая семья состоит, с точки зрения логики, из трех объектов: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе – это либо "не работает", либо указания кода работы и оклада.

Ясно, что для описания такой базы данных понадобится сложная область определения. Введем следующие структуры, соответствующие соответственно дате рождения члена семьи (число, месяц, год) и работе :

Domains

data=dat(integer,string,integer)

work=worker(string,integer);notwork

Тогда основная структура, соответствующая описанию каждого члена семьи, может выглядеть таким образом:

memfam=mem(string,string,data,work)

Информацию о семьях можно занести в базу данных с помощью следующих предложений:

family(mem(jon,kelly,dat(17,may,1950),worker(bbz,15000)),

mem(bony,kelly,dat(29,may,1951),notwork)),

[mem(pat,kelly,dat(5,april,1983),notwork),

mem(liz,kelly,dat(10,april,1960),notwork)).

family(mem(bob,rob,dat(14,may,1930),worker(pla,12000)),

mem(sally,rob,dat(5,october,1931),worker(plt,11000)),[ ]). % нет детей

Теперь из такой базы данных уже можно извлекать информацию. Так, в запросах к базе данных можно ссылаться на всех kelly с помощью терма:

goal family(mem(_,kelly,_,_),_,_).

Символы подчеркивания обозначают различные анонимные переменные, значения которых нас не интересуют.

Можно найти все семьи с тремя детьми при помощи выражения:

goal family(X,_, [_,_,_]).

Чтобы найти имена и фамилии всех женщин, имеющий по крайней мере трех детей, можно задать вопрос:

goal family(_, mem(Name,Fam,_,_),[_,_,_|_]).

Главным моментом в этих примерах является то, что указывать интересующие нас объекты можно не только по их содержимому, но и по их структуре, т.е. иметь результат в виде целой структуры или в виде отдельных элементов структур.

Можно также создать набор процедур, который делал бы взаимодействие с базой данных более удобным. Такие процедуры являлись бы частью пользовательского интерфейса. Вот некоторые из них:

husband(X):–family(X,_,_). % X – ìóæ

vife(X):–family(_,X,_). % X – жена

child(X):–family(_,_,Children), % X – ребенок

member(X,Children).

exist(X):–husband(X); vife(X); child(X). % X – любой член семьи

dohod(mem(_,_,_,worker(_,D)),D). % D – доход работающего

dohod(mem(_,_,_,notwork),0). % 0 – доход неработающего

Этими процедурами можно воспользоваться, например, в следующих запросах к базе данных:

1) найти имена и фамилии всех людей из базы данных:

Goal exist(mem(Nam,Fam,_,_)).

2) Найти всех работающих жен:

Goal vife(mem(Nam,Fam,_,worker(_,_))).

3) Найти фамилии людей, чей доход меньше чем 8000:

Goal exist(Man), dohod(Man,D), D<8000.

21. Задача "Ханойская башня". Имеется три стержня А,В,С. На стержне А лежит N дисков пирамидой, сужающейся кверху. Надо переместить диски со стержня А на стержень C, используя промежуточный стержень B и соблюдая законы:

1) диски можно перемещать с одного стержня на другой по одному;

2) нельзя класть больший диск на меньший;

3) при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды.

Если в программе использовать рекурсивную процедуру, то программа становится удивительно маленькой: два рекурсивных вызова процедуры и оператор вывода результатов перемещения дисков.

Собственно "перемещению" диска соответствует оператор вывода, указывающий, с какого стержня на какой переместить диск. Основным рабочим предикатом является рекурсивный предикат move. Базовое правило этой рекурсии: если диск один, то переместить его с левого стержня на правый. Иначе, переместить N-1 диск с левого диска на средний промежуточный, переместить один диск с левого стержня на правый и затем переместить N-1 диск со среднего стержня на правый, используя левый стержень как промежуточный.

domains

loc = right; middle; left

predicates

hanoi(integer)

move(integer, loc, loc, loc)

inform(loc, loc)

clauses

hanoi(N) :– move(N, left, middle, right). % Запуск программы

move(1, A, _, C) :– inform(A, C), !. % Переместить один диск

move(N, A, B, C) :– % Переместить N дисков

N1=N-1, move(N1, A, C, B),

inform(A, C), move(N1, B, A, C).

inform(Loc1, Loc2) :– write("\nMove a disk from ", Loc1, " to ", Loc2).

Goal hanoi(10). % Перемещаем 10 дисков

3.7. Динамическая база данных

Пролог поддерживает реляционную базу данных. Предикаты базы данных нужно объявлять в отдельном разделе Database. Программная секция Database должна предшествовать объявлению предикатов Predicates. Объявление предикатов базы данных аналогично их описанию в секции Predicates.

Динамическая база данных – раздел программы, в котором факты могут добавляться или загружаться из файла на диске во время выполнения программы или удаляться из нее. Факты, описывающие предикат базы данных, могут также обрабатываться как обыкновенные предикаты Пролога.

Для работы с базой данных используют стандартные предикаты asseta, assertz, retractall, consult, save и др. (см. раздел "Стандартные предикаты"). Также нужно иметь представление о структуре памяти системы Пролога. Исходная программа на Прологе хранится в области SOURSE, в то время как для размещения фактов динамической базы данных отведена область HEAP. Поэтому на экране нельзя видеть информацию, записанную в базу данных. Однако ее можно просмотреть как текстовый файл, если сохранить его в каталоге под своим именем.

С другой стороны, можно трактовать базу данных Пролога как некую глобальную переменную. Такая трактовка очень удобна: любая процедура может записывать в нее свой результат, который будет доступен любой другой процедуре, какая бы дистанция между ними ни была при их последовательных динамических вызовах.

22. Пример работы с динамической базой данных.

Domains

list=integer*

Database – db1 % База данных с именем db1

fact1(integer,string,list)

Database – db2 % База данных с именем db2

fact2(integer,string)

Clauses

fact1(1,f1,[1,2,3]).

fact1(2,f2,[1,3]).

fact1(3,f3,[2,2,1]).

fact2(1,],"one").

fact2(1,"one one"]).

fact2(2,"two").

Тогда цель:

Goal fact1(X,Y,Z)

ответит:

X=1 Y=f1 Z=[1,2,3])

X=2 Y=f2 Z=[1,3]).

X=3 Y=f3 Z=[2,2,1]).

3 solutions

Goal rettactall(fact1(X,Y,[_,2|Z])) % удалить факты по образцу

X=1 Y=f1 Z=3

X=3 Y=f3 Z=1

Goal retractall(fact1(X,Y,Z))

X=2 Y=f2 z=[1,3]

Goal retractall(db2) % удалить поименованную базу данных

Yes .

23. Программа классификации. Здесь мы рассмотрим вопросно-ответную систему, которая является примером маленькой экспертной системы в том смысле, что программа варьирует процесс опроса в зависимости от обстоятельств; более того, она может задавать минимально необходимое число вопросов.

Основой базы данных такой программы является дерево решений некоторой предметной области. В нашем случае таким деревом будет система классификации животных. Все животные делятся на млекопитающих, птиц и рыб. Среди млекопитающих могут быть хищники и копытные. К хищникам, в частности, относятся тигр и гепард.

Приведем здесь пример версии программы с обратной цепочкой рассуждений, т.к. она ближе к встроенному в Пролог механизму вывода. Программу с прямой цепочкой рассуждений можно посмотреть в [1].

Структура версии с обратной цепочкой рассуждений проектируется введением группы правил высокого уровня. Каждое такое правило описывает одно животное, например:

animal_is("гепард") :– it_is("млекопитающее"),

it_is("хищник"),

positive("имеет","рыжий цвет"),

positive("имеет", "черные пятна").

animal_is(“тигр”) :– it_is(“млекопитающее”),

it_is(“хищник”),

positive(“имеет”, “рыжий цвет”),

positive(“имеет”, “черные полосы”).

animal_is("зебра") :– it_is("копытное"),

positive("имеет","черные полосы").

animal_is("пингвин") :– it_is("птица"),

negative("умеет", "летать"),

positive("умеет", "плавать"),

positive("имеет", "черно-белый цвет").

Сходные правила должны быть для всех животных, которых предстоит классифицировать программе.

Все правила поддерживаются на следующем, более низком уровне некоторыми соподчиненными предикатами:

it_is("хищник") :–

positive("имеет","острые зубы"),

positive("имеет", "когти"),

positive("имеет", "глаза, направленные вперед").

it_is("копытное") :–

it_is("млекопитающее"),

positive("имеет","копыта"),

positive("æóåò", "æâà÷êó").

Свою работу программа начинает с использования правила

Goal animal_is(X), !,

write("Задуманное вами животное ",X).

Далее система пытается по очереди установить истинность или ложность правил высокого уровня, т.е. найти кандидата, которого она сможет проверить на соответствие предикату animal_is.

Определение истинности такого правила влечет за собой проверку всего дерева подчиненных фактов и свидетельств, которые должны быть истинными, чтобы подтвердить основное заключение. По мере продвижения вниз по дереву программа соответственно ситуации задает нужные вопросы в нужное время для получения недостающей информации, поэтому ее поведение кажется разумным. Большая часть работы совершается правилами positive и negative, xpositive и xnegative. Они используются для проверки конкретных атрибутов животных, которые могут быть обнаружены в процессе диалога и записаны в базу данных.

Здесь задействован механизм вопросов-ответов, поэтому нам необходимо подробно рассмотреть эти правила. Ниже следует соответствующая часть программы.

database

xpositive(symbol, symbol)

xnegative(symbol, symbol)

Clauses

positive(X, Y) :– % Положительный ответ обнаружен

xpositive(X, Y), !. % в базе данных

positive(X,Y):–xnegative(X,Y),!,fail. % Отрицательный ответ обнаружен

positive(X, Y) :– % Задается вопрос, для которого

not(xnegative(X, Y)), % ожидается положительный ответ

ask(X, Y, yes),!.

ask(X, Y, yes) :–

write(X, " оно ", Y, '\n'),

readchar(Reply),

ans_pos(X, Y, Reply).

ans_pos(X,Y,'y'):– assertz(xpositive(X,Y)).

ans_pos(X,Y,'n'):– assertz(xnegative(X,Y)), !, fail.

Когда механизм вывода доходит до места, где требуется узнать, был ли установлен некоторый атрибут животного, он использует правила positive и negative. (Здесь у нас приведен предикат positive, соответствующий положительному значению атрибута. Сходный по работе с ним предикат negative записывается симметрично.)

Первая из статей предиката positive заставляет систему непосредственно просмотреть информацию, уже включенную в базу данных. Если атрибут в ней найден, процесс заканчивается. Второе правило этого предиката инициирует поиск отрицания того, что мы пытаемся установить, и если оно найдено, значение атрибута становится ложным, система переходит к проверке следующего правила animal_is. Если же фактов нет среди истинных и ложных, программа задает вопрос пользователю, при этом любой полученный ответ запоминается с целью непосредственного или последующего применения.

Все, что программа помещает в базу данных, всегда имеет вид пары, состоящей из глагола и свойства, например:

positive("имеет","перья").

Поэтому легко создать грамматически правильное предложение для предъявления его пользователю, поставив слово "оно" между глаголом и свойством. Пользователь, вероятно, введет символы "y" или "n" в ответ на запрос, а запоминающее правило занесет информацию в базу данных посредством одного из двух предикатов:

xpositive(verb,,attribute)

xnegative(verb,attribute).

Поэтому если вы хотите перезапустить программу, то сначала надо очистить базу данных от ответов на вопросы, заданные при ведении последнего диалога. Они продолжают находиться в базе данных и будут влиять на следующие результаты, если их не удалить.

3.8. Обработка текстов

Пролог обладает большими возможностями по сопоставлению объектов с образцом, поэтому данный язык программирования хорошо подходит для обработки текстов. На Прологе с успехом можно реализовывать генераторы отчетов, текстовые редакторы и трансляторы с языков.

В данном разделе продемонстрируем две системы грамматического разбора. Система грамматического разбора – это программа, которая распознает синтаксические объекты в потоке лексем, т.е. реализует какую-либо формальную грамматику. Общеизвестны две основные стратегии грамматического разбора: нисходящая (сверху вниз) и восходящая (снизу вверх).

Система нисходящего грамматического разбора базируется на стратегии с обратной цепочкой рассуждений, а система восходящего разбора – с прямой. Следовательно, реализация на Прологе системы нисходящего разбора может быть осуществлена достаточно прямолинейным способом.

Продемонстрируем систему разбора сверху вниз примером простейшего синтаксического анализатора предложений. В описанной системе используется грамматика, которую можно схематически представить так:

предложение --> группа_подлежащего группа_сказуемого

группа_подлежащего --> определение существительное

группа_подлежащего --> существительное

группа_сказуемого --> глагол существительное

Первым аргументом предиката object является входной список лексем, третий аргумент – это название определяемого объекта. Второй аргумент образован частью списка, оставшегося после того, как из оставшегося списка будет взят терминал или нетерминал.

Система нисходящего грамматического разбора начинает работу с принятия некоторой гипотезы, а затем проверяет верность следствий этой гипотезы по данным, содержащимся во входном списке. Первоначальной гипотезой может служить, например, предположение о том, что во входном списке можно обнаружить нетерминал "предложение". В соответствии с грамматическим правилом для нетерминала "предложение" данная гипотеза разбивается на две субгипотезы: на предположения о том, что во входном потоке содержатся группа подлежащего и группа сказуемого. Эти две гипотезы в свою очередь разбиваются на субгипотезы более низкого уровня. Процесс разделения гипотез на субгипотезы продолжается до тех пор, пока система не встретит терминал. В этом случае она пытается установить факт наличия терминала в начальной позиции входного списка.

Несколько сложнее реализуется на Прологе система восходящего грамматического разбора, т.к. она базируется на прямой цепочке рассуждений. Однако такая система имеет то преимущество, что может работать с рекурсивными правилами, которые могли бы вызвать бесконечное зацикливание в системе нисходящего разбора.

Примером для реализации восходящей грамматики с рекурсивными правилами является синтаксический анализатор математических выражений. Такая система начинает работу с данными и переходит к простым синтаксическим объектам, а затем и к более сложным. В то время как система нисходящего разбора управляется в основном гипотезами, система восходящего грамматического разбора управляется данными.

Более важной сферой применения систем грамматического разбора является построение так называемого дерева грамматического разбора в том или ином виде, в котором явно указаны классы объектов и существующие между ними отношения

24. В следующем примере на вход подается алгебраическое выражение в виде строки, которое может содержать имена переменных и знаки плюс и умножить. Результат работы программы – запись выражения в префиксной форме, когда знак операции предшествует операндам.

Предикат run начинает работу программы с создания окна, считывает исходное выражение в переменную STR . Следующий предикат tokl переводит строковую переменную в список токенов (лексем) TOKL, далее предикат s_exp запускает рабочий предикат plusexp, с которого собственно начинается работа анализатора.

Процедура multexp первую лексему (имя переменной) переводит в префиксную форму и проверяет остаток на наличие после нее (лексемы) операции умножения предикатом multexp1. Если знак "*" присутствует, последний предикат переводит сомножители в префиксную форму.

Предикат plusexp1 проверяет остаток после знака "+" на наличие операции умножения предикатом multexp. Если умножения нет, слагаемые также переводятся в префиксную форму.

domains

TOKL = STRING*

EXP=var(STRING);

plus(EXP,EXP);

mult(EXP,EXP)

PREDICATES

run

tokl(STRING,TOKL)

s_exp(TOKL,TOKL,EXP)

multexp(TOKL,TOKL,EXP)

multexp1(TOKL,TOKL,EXP,EXP)

plusexp(TOKL,TOKL,EXP)

plusexp1(TOKL,TOKL,EXP,EXP)

elmexp(TOKL,TOKL,EXP)

GOAL

run.

CLAUSES

run:– makewindow(1,2,7,"",0,0,25,80),

readln(STR),tokl(STR,TOKL),

s_exp(TOKL,_,EXP), write(EXP),nl.

tokl(STR,[TOK|TOKL]):–

fronttoken(STR,TOK,STR1),

tokl(STR1,TOKL).

tokl(_,[]).

s_exp(IL,OL,EXP):–plusexp(IL,OL,EXP).

plusexp(IL,OL,EXP2):–

multexp(IL,OL1,EXP1),

plusexp1(OL1,OL,EXP1,EXP2).

plusexp1(["+"|IL],OL,EXP1,EXP3):–

multexp(IL,OL1,EXP2),

plusexp1(OL1,OL, plus(EXP1,EXP2),EXP3).

plusexp1(IL,IL,EXP,EXP).

multexp(IL,OL,EXP2):–

elmexp(IL,OL1,EXP1),

multexp1(OL1,OL,EXP1,EXP2).

multexp1(["*"|IL],OL,EXP1,EXP3):–

elmexp(IL,OL1,EXP2),

multexp1(OL1,OL, mult(EXP1,EXP2),EXP3).

multexp1(IL,IL,EXP,EXP).

elmexp([NAME|IL],IL, var(NAME)).

25. Еще один пример анализатора, строящего дерево синтаксического разбора для простого английского выражения. Предложение, подлежащее разбору, должно соответствовать следующей грамматике:

<VERB PHRASE> ::= <verb> | <NOUN PHRASE>

Программа на Прологе:

DATABASE %Слова , которые должны быть распознаны

det( STRING ) % Определитель

noun( STRING ) % Существительное

rel( STRING ) % Предлог

verb( STRING ) % Глагол

DOMAINS % Описание грамматики

DETERM = none ; determ( STRING )

NOUNP = nounp( DETERM, STRING, RELCL)

RELCL = none ; relcl( STRING, VERBP )

SENTENCE = sent( NOUNP, VERBP )

VERBP = verb( STRING ) ; verbp( STRING, NOUNP )

TOKL = STRING*

PREDICATES

is_det( STRING )

is_noun( STRING )

is_rel( STRING )

is_verb( STRING )

s_determ( TOKL, TOKL, DETERM )

s_nounp( TOKL, TOKL, NOUNP )

s_relcl( TOKL, TOKL, RELCL )

s_sentence( TOKL, TOKL, SENTENCE )

s_verbp( TOKL, TOKL, VERBP )

tokl( STRING, TOKL )

tom(TOKL)

run1

run2(STRING)

sen_an

GOAL makewindow(1,6,0,"",0,0,25,80),

sen_an.

CLAUSES

sen_an:– write("Try: every man that lives loves a woman"),

readln(LIN), LIN >< "" ,

tokl(LIN,TOKL),

s_sentence( TOKL, _, SENT),

write("PROLOG OBJECT=",SENT," "),

readchar(_),clearwindow,!.

tokl(STR,[TOK|TOKL]) :–

fronttoken(STR,TOK,STR1),

tokl(STR1,TOKL).

tokl(_,[ ]).

s_sentence(TOKL,TOKL2,sent(NOUNP,VERBP)):–

s_nounp(TOKL,TOKL1,NOUNP),

s_verbp(TOKL1,TOKL2,VERBP),

TOKL2=[ ],!.

s_sentence(_,_,_):–write(">> Sentence not recognized \n"),fail.

% Группа подлежащего

s_nounp(TOKL,TOKL2,nounp(DETERM,NOUN,RELCL)):–

s_determ(TOKL,[NOUN|TOKL1],DETERM),

is_noun(NOUN),

s_relcl(TOKL1,TOKL2,RELCL).

% Определитель

s_determ([DETERM|TOKL],TOKL,determ(DETERM)):–

is_det(DETERM).

s_determ(TOKL,TOKL,none).

% Группа дополнения

s_relcl([REL|TOKL],TOKL1,relcl(REL,VERBP)):–

is_rel(REL),

s_verbp(TOKL,TOKL1,VERBP).

s_relcl(TOKL,TOKL,none).

% Группа сказуемого

s_verbp([VERB|TOKL],TOKL1,verbp(VERB,NOUNP)):–

is_verb(VERB),

s_nounp(TOKL,TOKL1,NOUNP).

s_verbp([VERB|TOKL],TOKL,verb(VERB)):–

is_verb(VERB).

is_noun(X):–noun(X),!.

is_noun(X):–noun(Y),concat(Y,"s",X).

is_det(X):–det(X).

is_rel(X):–rel(X).

is_verb(X):–verb(X),!.

is_verb(X):–verb(Y),concat(Y,"s",X),!.

is_verb(X):–verb(Y),concat(Y,"ed",X),!.

is_verb(X):–verb(Y),concat(Y,"es",X),!.

is_verb(X):–verb(Y),concat(Y,"ing",X).

% Словарь

det("every").

det("a").

noun("man").

noun("woman").

rel("that").

rel("who").

rel("whom").

rel("which").

rel("that").

verb("love").

verb("live").

4. Стандартные предикаты

Одной из основных причин, которые помогли Прологу стать "реальным" языком программирования, было введение в язык элементов, лежащих за пределами чистой логики. В Турбо-Прологе такие элементы реализованы как стандартные (встроенные) предикаты.

Большинство стандартных предикатов выполняет несколько функций в зависимости от состояния параметров, входящих в предикат. В одном случае заранее определен какой-либо один параметр, в другом случае известны другие параметры, иногда к моменту обращения могут быть известны все параметры. Известные параметры предиката называются входными, неизвестные – выходными. Совокупность входных и выходных параметров определяет работу предиката. Эта совокупность называется поточным шаблоном. Если предикат будет вызываться с двумя аргументами, имеется четыре варианта поточного шаблона:

(i,i) (i,o) (o,i) (o,o),

где i – входной параметр, о – выходной параметр. Однако не для каждого предиката все возможные варианты поточного шаблона имеют смысл.

Hиже приводятся некоторые наиболее часто употребляемые стандартные предикаты, сгруппированные в отдельные классы по их функциональному назначению. Более полный список стандартных предикатов можно найти в [3].

4.1. Ввод/вывод

readln(StringVariable)

(string) – (o)

Считывает строку с текущего устройства ввода и связывает ее с заданной переменной StringVariable. Обычно чтение производится с клавиатуры. В качестве конца строки используется символ возврата каретки. Readln считывает до 150 символов в строке при вводе с клавиатуры и до 64К при вводе с других устройств.

readint(IntgVariable)

(integer) – (o)

Читает целое число с текущего устройства ввода и связывает его с заданной переменной.

readreal(RealVariable)

(real) – (o)

Читает действительное число с текущего устройства чтения и связывает его с заданной переменной RealVariable. Обычно чтение производится с клавиатуры.

readchar(CharVariable)

(char) – (o)

Читает символ с текущего устройства ввода и связывает его с заданной переменной CharVariable. В отличие от inkey устанавливает режим ожидания ввода.

inkey(CharVariable)

(Char) – (o)

Читает символ со стандартного устройства ввода. В отличие от предиката readchar выполнение программы не прерывается. Поэтому inkey применяют главным образом для организации циклов ожидания.

keypressed

Выполняется успешно, если нажата некоторая клавиша. В отличие от предиката inkey с помощью keypressed можно установить, нажата ли клавиша, не читая при этом введенный с клавиатуры символ.

write( Variable|Constant * )

Запись заданных значений переменных и констант в заданное активное окно на текущем устройстве вывода.

Вызывает возврат каретки и перевод строки.

4.2. Управление экраном и оконная система

Пролог позволяет управлять следующими характеристиками экрана: инверсным изображением, подчеркиванием и цветом. Эта информация задается в стандартных предикатах посредством значений атрибутов. Можно задавать цвет переднего плана и фона, а также отдельных символов и всего экрана.

В таблице, приведенной ниже, даны значения атрибутов для цветного графического дисплея.

Фон	Передний план
Черный 0	Черный 0
Голубой 16	¦Голубой 1
Зеленый 32	Зеленый 2
Бирюзовый 48	Бирюзовый 3
Красный 64	Красный 4
Алый 80	Алый 5
Коричневый 96	Коричневый 6
Белый 112	Белый 7

Кроме того, при сложении значения атрибута с 1 символы подчеркиваются. Сложение значения атрибута с 8 усиливает интенсивность цвета. При сложении значения атрибута со 128 происходит мерцание символов.

Пролог поддерживает развитую оконную систему. Для ее организации используются следующие стандартные предикаты:

makewindow(WindowNo, ScrAtt, FrameAtt, Framestr, Row, Column, Height, Width)

(integer,integer,integer,string,integer,integer,integer,integer)

- (i,i,i,i,i,i,i,i) (o,o,o,o,o,o,o,o)

Определяет для (i,i,i,i,i,i,i,i) область экрана в качестве окна. Каждое окно задается номером WindowNo. ScrAtt задает значение атрибута для всех позиций описываемого окна. Если FrameAtt не равно 0, окно берется в рамку и верхняя граница включает текст Framestr. Позиция левого верхнего угла окна задается параметрами Row и Col. Параметры Height и Width определяют соответственно высоту и ширину окна, которые должны быть совместимыми с размерами экрана. В случае (о,о,о,о,о,о,о,о) связывает характеристики текущего окна с выходными параметрами.

shiftwindow(WindowNo)

(integer) – (i) (o)

Активизирует (i) окно с номером WindowNo. Окно должно быть создано заранее. Связывает (o) c параметром "номер текущего окна".

removewindow

Удаляет текущее активное окно.

clearwindow

Очищает текущее активное окно.

cursor(Row,Column)

(integer,integer) – (i,i) (o,o)

Для (i,i) помещает курсор в позицию с координатами (Row,Column) или присваивает переменным Row и Column значения текущих координат курсора при (o,o).

4.3. Обработка строк

Предикаты обработки строк используются для разделения строк либо на список отдельных символов, либо на список заданных групп символов.

frontchar(String,FrontChar,RestString)

(string,char,string) – (i,o,o) (i,i,o) (i,o,i) (i,i,i) (o,i,i)

Разделяет заданную строку String согласно поточному шаблону на две части: первый символ FrontChar и оставшаяся часть строки RestString.

fronttoken(String,Token,RestString)

(string,string,string) – (i,o,o) (i,i,o)(i,o,i) (i,i,i) (o,i,i)

Разделяет строку, заданную параметром String, на лексему Token и остаток RestString согласно поточному шаблону. (Лексема – это последовательность символов, имеющих смысл. Она определяется либо как имя в соответствии с синтаксисом Турбо-Пролога, либо как строчное представление числа, при этом знак возвращается отдельно, либо как отдельный символ.)

frontstr(Lenght,Inpstring,StartString,RestString)

(integer,string,string,string) – (i,i,o,o)

Разделяет строку Inpstring на две части. StartString будет иметь длину Lenght первых символов исходной строки, RestString представляет собой остаток строки InpString.

concat(String1,String2,String3)

(string,string,string) – (i,i,o) (i,o,i) (o,i,i) (i,i,i)

Слияние строк , согласно поточному шаблону, по формуле: String3 = String1 + String2.

str_len(String,Length)

(string,integer) – (i,i) (i,o) (o,i)

Определяет длину Length строки String.

isname(StringParam)

(string) – (i)

Завершается успешно, если StringParam есть имя, удовлетворяющее синтаксису Пролога.

4.4. Преобразование типов

Стандартные предикаты данной группы служат для преобразования символов с десятичным кодом ASCII, строк с отдельным символом, строк с целыми и действительными числами, а также строчных букв латинского алфавита с соответствующими прописными буквами.

char_int(CharParam,IntgParam)

(char,integer) – (i,o) (o,i) (i,i)

Преобразует символ в код ASCII, согласно поточному шаблону.

str_int(StringParam,IntgParam)

(string,integer) – (i,o) (o,i) (i,i)

Строка, представляющая целое десятичное число, преобразуется в это число.

str_char(StringParam,CharParam)

(string,char) – (i,o) (o,i) (i,i)

Один знак как строка преобразуетс в символ.

str_real(StringParam,RealParam)

(string,real) – (i,o) (o,i) (i,i)

Строка, представляющая десятичное число, преобразуется в это число.

4.5. Работа с базой данных

consult(DosFileName)

(string) – (i)

Добавляет текстовый файл с именем DosFileName к текущей базе данных. Текстовый файл может быть, например, создан в результате выполнения предиката save. Этот файл содержит факты, которые должны быть описаны в разделе DbaseDom. Выполнение предиката не будет успешным, если в файле имеются синтаксические ошибки.

save(DosFileName)

(string) – (i)

Записывает динамическую базу данных на диск в текстовый файл с именем DosFileName. После этого файл можно снова загрузить в оперативную память, используя предикат consult. Для хранения каждого факта используется отдельная строка. Текстовый файл, представляющий собой всю базу данных, можно просмотреть и изменить, используя редактор Пролога.

asserta( Term )

(DbaseDom) – (i)

Заносит факт Term в базу данных перед другими фактами. Факт должен быть термом, принадлежащим области определения DbaseDom.

assertz( Term )

(DbaseDom) – (i)

Заносит факт Term в конец базы данных. Факт должен быть термом, принадлежащим области определения DbaseDom.

retract( Term )

(DbaseDom) – (_)

Удаляет первый факт из базы данных, который соответствует заданному факту Term.

retractall(Term)

(InternalDatabaseDomain) – (_)

Очищает всю базу данных.

4.6. Управляющие предикаты

exit

Выполняет немедленный выход из программы.

fail

Вынуждает завершиться предикат ложно и, следовательно, возвратиться к предыдущей точке разветвления (backtracking).

true

Значение предиката всегда истинно.

Отсечение (прекращение перебора между головой дизъюнкта и данным знаком).

4.7. Прочие стандартные предикаты

random(RealVariable)

(real) – (o)

Равномерное псевдослучайное число в диапазоне от 0 до 1.

random(MaxValue,RandomInt)

(integer,integer) – (i,o)

Равномерное псевдослучайное целое число RandomInt в диапазоне от 0 до MaxValue.

findall( Variable, Atom, ListVariable )

В списке ListVariable возвращаются все решения для переменной Variable в предикате Atom.

not( Atom )

Выполняется успешно, если заданный Atom представляет собой цель, которая не достигается.

free( Variable )

Выполняется успешно, если Variable не является конкретизированной переменной.

bound( Variable )

Выполняется успешно, если Variable является конкретизированной переменной.

4.8. Арифметические и логические предикаты

В арифметических операциях могут участвовать операнды (числа и переменные), арифметические операции + (сложение), – (вычитание), * (умножение), / (деление), mod (деление по модулю), div (целочисленное деление), скобки.

Приоритет выполнения операций представлен числами:

+ , –	1
* , /	2
div ,mod	3
– ,+ (унарные)	4

Логические операторы:

>	Бодьше
<	Меньше
=	Равно
>=	Больше или равно
<=	Меньше или равно
<> ,	Не равно

Арифметические функции:

sin(Х)	Синус, угол в радианах
cos(Х)	Косинус, угол в радианах
tan(Х)	Тангенс, угол в радианах
arctan(Х)	Арктангенс
ln(Х)	Логарифм натуральный
log(Х)	Логарифм десятичный
abs(X)	Модуль аргумента
exp(Х)	Экспонента
sqrt(Х)	Корень квадратный

Кроме этих предикатов, в Прологе имеется большой набор стандартных предикатов для построения графических объектов. Просмотреть названия стандартных предикатов графики можно в разделе HELP меню интегрированной среды Пролога.

Часть 2. Лабораторные работы

Лабораторная работа №1. Общие сведения об языке логического программирования

Пример 1. Наша первая Пролог программа будет содержать информацию о военнослужащих некоторого воинского подразделения и их званиях: “Павлов генерал”, “Сабо полковник”, “Денисов капитан”, “Матвеев капитан”, “Кулёмин сержант”, “Николаев сержант”. Сформулировать на Прологе следующие вопросы: 1) Павлов генерал? 2) Кто является полковником? 3)Кем является Денисов? 4)В подразделение есть военный в звание сержанта? 5) В подразделение есть военный в звание подполковника? 6) Вывести военных, имеющих одинаковые звания.

В программе каждого военного мы представим предикатом military размерности 2, каждый компонент- атом, первый представляет фамилию, а второй – его звание.

Программа 3. База данных «Военная часть»

Domains

s=symbol

Predicates

military(s,s)

Clauses

military(pavlov, general).

military(sabo, polkovnik).

military(denisov, kapitan).

military(matveev, kapitan).

military(kulemin, serzhant).

military(nikolaev, serzhant).

Сформулируем запросы:

1) ? military(pavlov, general)

Ответ: yes

2) ? military(X, polkovnik)

Ответ: X= sabo

3) ? military(denisov, X)

Ответ: X= kapitan

4) ? military(_, serzhant)

Ответ: yes

5)? military(_, podpolkovnik)

Ответ: no

6) ? military(X,Y), military(Z, Y), X<>Z

Ответ: X= denisov Z= matveev Y= kapitan

X= kulemin Z= nikolaev Y= serzhant

Пример 2. Данные о крупных реках России сведены в таблицу:

Таблица 5.

Данные о крупных реках России

Название реки	Длина, км	Годовой сток, км³	Площадь бассейна, тыс. км²	Истоки	Куда впадает
Амур	4416	350	1855	Яблоневый хребет	Татарский пролив
Лена	4400	488	2490	Байкальский хребет	Море Лаптевых
Обь	4070	400	2990	Предгорья Алтая	Карское море
Иртыш	4248	323	1643	Китай	Обь
Енисей	3487	600	2580	Восточный Саян	Карское море
Волга	3530	255	1360	Валдайская возвышенность	Каспийское море
Колыма	2129	44	643	Хребет Черского	Восточносибирское море
Урал	2428	54	231	Южный Урал	Каспийское море
Дон	2200	45	504	Среднерусская возвышенность	Азовское море
Кама	1805	130	507	Верхне — Камская возвышенность	Волга
Печора	1809	130	322	Северный Урал	Баренцево море
Ангара	1779	62	1039	Байкал	Енисей
Селенга	1024	14	447	Монголия	Байкал
Кубань	870	11	58	Кавказ	Азовское море

Составить базу данных и ответить на следующие вопросы:

1) Определить реки, впадающие в Азовское море.

2) Определить реки, исток которых находится на Валдайской возвышенности?

3) Какие реки короче Камы?

4) Какие реки длиннее Иртыша?

5) Как задать вопрос, определяющий все данные о реке Кама?

Программа 4. База данных «Реки России»

Domains

S=symbol

N=integer

Predicates

reka(S,N,N,N,S,S)

Clauses

reka(amur, 4416, 350, 1855,yablonevi_hrebet,tatar_proliv).

reka(lena, 4400, 488, 2490, baikal_hrebet, more_laptevih).

reka(ob, 4070, 400, 2990, altai, more_karskoe).

reka(irtish, 4248, 323, 1643, kitai, ob).

reka(enisei, 3487, 600, 2580, vost_cain, more_karskoe).

reka(volga, 3530, 255, 1360, valdais_vozvishennost, more_kaspi).

reka(kolima, 2129, 44, 643, hrebet_cherskogo, vost_sibir_more).

reka(ural, 2428, 54, 231, yuzhni_ural, more_kaspi).

reka(don, 2200, 45, 504, sredn_rus_vozvvishennost, more_azov).

reka(kama, 1805, 130, 507, verhne_kamsk_ vozvvishennost, volga).

reka(pechora, 1809, 130, 322, sever_ural, barenzevo_more).

reka(angara, 1779, 62, 1039, baikal, enisei).

reka(selenga, 1024, 14, 447, mongolia, baikal).

reka(kuban, 870, 11, 58, kavkaz, more_azov).

Запросы:

reka(X, _, _, _, _, more_azov)

reka(X, _, _, _, valdais_vozvishennost,_)

reka(X, Y, _, _, _, _), reka(lena, Z, _, _, _, _), Y<Z

reka(X, Y, _, _, _, _), reka(irtish, Z, _, _, _, _), Y>Z

reka(kama, A,B,C,D,E)

Пример 3. Известно, что Лене нравится теннис, Денису нравится футбол, Борису – бейсбол, Эдику – плавание, Марку нравится теннис, а Фёдору то, что нравится Борису. Записать факты на Прологе и ответить на вопросы: 1)Кому нравится теннис? 2) Что нравится Федору? 3)Кто занимается одинаковыми видами спорта?

Программа 5. База знаний «Предпочтения»

Predicates

likes(symbol,symbol)

Clauses

likes(lenа, tennis).

likes(denis, football).

likes(boris, baseball).

likes(edic, swimming).

likes(mark, tennis).

likes(fedor, Activity):- likes(boris, Activity).

/* Activity играет роль переменной*/

Запросы

1) ? likes(X, tennis)

Ответ:

X= lenа

X= mark

2) ? likes(fedor, X)

Ответ:

X= baseball

3) ? likes(X, T), likes(Y, T)

Ответ:

X= lenа Y= mark T= tennis

X= mark Y= lenа T= tennis

X= boris Y= fedor T= baseball

X= fedor Y= boris T= baseball

Пример 4. Лена, Анна, Денис и Борис-люди, лада и нисан - автомобили, Лене нравится лада, Анне - пицца, Денису - футбол, а Борис - Мерседес, Ваське - рыбка. Пицца, лада, мерседес продаются. Человек может купить машину, если она продается, и она ему нравится. Сформулировать на прологе вопросы: 1)Какую машину может купить Лена? 2) Кто-нибудь может купить мерседес? 3) какие машины продаются, и ответить на них.

Программа 6. База знаний «Предпочтения и возможности»

Domains

s=symbol

Predicates

human(s)

car(s)

likes(s,s)

can_by(s,s)

cells(s)

Clauses

human( lena ).

human( anna ).

human( denis ).

human( boris ).

car( lada ).

car( nissan ).

likes( lena, lada ).

likes( anna, pizza ).

likes( denis, football ).

likes( boris, mersedes ).

likes( vasya, ribka ).

cells(pizza).

cells(lada).

cells(mersedes).

can_by(X,Y):-human(X), car(Y), likes(X,Y), cells(Y).

Запросы:

1) can_by(lena, X)

X=lada

2) can_by(_,mersedes)

3) car(X),cells(X)

X=lada

Пример 5. Программа иллюстрирует различные способы ввода данных.

Программа 7. Ввод данных

Predicates

vvod_int

vvod_ch

vvod_s

Clauses

vvod_int:- readint(N1), readint(N2), N=N1+N2, write(N).

vvod_ch:- readchar(N1), readchar(N2), N=N1+N2, write(N).

vvod_s:- readln(N1), readln(N2), concat(N1,N2,N), write(N).

Пример 6. Вывести в каждой строке сообщения: Леонард отец Катерины, Карл отец Джейсона, Карл отец Марины.

Программа 8. База знаний «Семья»

Domains

name = symbol

Predicates

father(name, name)

everybody

clauses

father(leonard, katherine).

father(carl, jason).

father(carl, marinа).

everybody :-

father(X, Y),

write(X, " is ", Y, "s father\n"),

fail.

В некоторых случаях может быть необходимым продолжение поиска дополнительных решений, для этого можно использовать встроенный предикат fail. Он не имеет аргументов, всегда считается ложным.

Проверьте работу программы с и без использования предиката fail.

Отрицание задается с помощью предиката not.

Пример 7. У нас есть информация о странах-партнерах Европы, имеющих общую границу. Предположим, нас интересуют какие страны-партнеры не имеют общей границы.

Программа 9. База знаний «Страны Европы»

Domains

country=symbol

Predicates

euro_pair(country, country)

border(country, country)

find_non_border_pair

Clauses

euro_pair(”France”, ”Germany”).

euro_pair(”France”, ”Spain”).

euro_pair(”France”, ”Italy”).

euro_pair(”Germany”, ”Spain”).

euro_pair(”Germany”, ”Italy”).

euro_pair(”Spain”, ”Italy”).

border(”France”, ”Germany”).

border(”France”, ”Spain”).

border (”France”, ”Italy”).

find_non_border_pair:-

euro_pair(X,Y),

not(border(X,Y)),

write(X,” – “,Y),fail,nl.

Goal

find_non_border_pair

Результатом запроса будет ответ

Germany - Spain. Germany - Italy. Spain - Italy.

Пример 8. Использование составных объектов

Программа 10. База данных «Коллекция»(Вариант 1)

Domains

personal_library=book(title, author, publisher, year)

collector, title, author, publisher=symbol

year=integer

Predicates

collection(collector, personal_library)

Clauses

collection(ivanov, book(”Zolushka”, ”Denis Tarakanov”, ”Dinamo”, 2003)).

collection(petrov, book(”Maslenniza”, ”Anna Zimina”, ”Zenit”, 2005)).

collection( petrov, book(”Repka”,”Irina Larina”, ”Mir”, 1999)).

/*Демонстрация двухуровневого составного объекта*/

Программа 11. База данных «Коллекция»(Вариант 2)

Domains

personal_library=book(title, author, publiсation)

publiсation= publiсation (publisher, year)

collector, title, author, publisher =symbol

year=integer

Predicates

collection(collector, personal_library)

Clauses

collection(ivanov,book(”Zolushka”,”Den Taran”, publiсation (”Dina”, 2003))).

collection(petrov,book(”Maslenniza”,”Anna Zima”,publiсation(”Zenit”,2005))).

collection( petrov, book(”Repka”,”Irina Larina”,publiсation (”Mir”, 1999))).

/*Демонстрация использования конструкций альтернативных доменов*/

Программа 12. База знаний «Клуб по интересам»

Domains

thing=misc_ thing (whatever);

book(author, title);

record(artist, album, type)

person, whatever, title, author,artist, album, type =symbol

Predicates

owns(person, thing)

show_misc_things

show_books

show_records

Clauses

owns (“Ivanov“, misc_things(“sports car“)).

owns (“Petrov“, misc_things(“motor cycle“)).

owns (“Smirnov“, misc_things(“piano“)).

owns (“Ivanov”, book (“James A.Mishener“,“Space“)).

owns (“Petrov”, book (“Frank Herbert“, “Dune“)).

owns (“Sidorov”, book (“J.R.R. Tolkein“,“Return of the Ring“)).

owns (“Ivanov”, record (“Elton John”, “Ice Fair”, “popular“)).

owns (“Petrov”, record(“Michael Jackson“, “We are the World“, “popular“)).

owns (“Sidorov”, record (“Madonna“,“Madonna“, “popular“)).

show_misc_things:- owns (X, misc_things(Y)),write( X, “ ”,Y), nl, fail.

show_books:- owns (X, book (_,Y)),write( X, “ ”,Y), nl, fail.

show_records:- owns (X, record (_,Y,_)),write( X, “ ”,Y), nl, fail.

Задания для самостоятельной работы

Вариант1.Дана база данных “Родители и дети”:

родитель(полина, борис), родитель(анатолий, борис), родитель(анатолий, лиза), родитель(борис, катя), родитель(борис, валентина), родитель(полина, евгений).

Сформулировать вопросы на Прологе: Кто является родителем Кати? Есть ли у Лизы ребенок? Кто дети Бориса? Кто чей родитель?

Вариант 2.Дана база данных “Теремок”:

живет (муха, горюха), живет(комар, пискун), живет(мышка, погрызуха), живет(лягушка, квакушка), живет(заюнок, кривоног),

живет( лиса, краса), живет(волк, хватыш), не_живет(медведь, пригнетыш).

Указать ответы на следующие вопросы:

?-живет(мышка, погрызуха). ? -живет(волк, X).

?-живет(Х, кривоног). ?-не_живет(М,P).

Сформулировать вопросы на Прологе: Живет ли лягушка в теремке? Какое прозвище у лисы? Кто имеет прозвище горюха? Какой следует задать вопрос, чтобы узнать обитателей теремка (без прозвищ)?

Вариант 3.База данных “Рождение и хобби друзей”:

рождение(иванова, лена, 22, июнь, 1971), рождение(петров, сергей, 25, октябрь, 1973), рождение(сидорова, оля, 1, декабрь, 1974), любит(иванова, лена, книги), любит(иванова, лена, танцы), любит(петров, сергей, видео), любит(сидорова, оля, кино).

Сформулировать вопросы на Прологе: Кто родился в 1971 году? Кто родился в октябре? Кто любит книги? Кто любит и книги и танцы?

Вариант 4. База данных “Колобок”: ушел(колобок,дедушка), ушел(колобок, бабушка), ушел(колобок, заяц), ушел(колобок, волк), ушел(колобок, медведь), не_ушел(колобок, лиса).

Сформулировать вопросы на Прологе: Кто ушел от волка? Кто не ушел от лисы? Кто ушел от волка и от бабушки? Какой следует задать вопрос, чтобы узнать всех персонажей сказки?

Вариант 5 База данных “Распорядок дня”:

занятие (0, 7, сон), занятие (7, 8, завтрак), занятие (8, 13, школа), занятие (13, 14, обед), занятие (14, 19, свобода), занятие (19, 20, ужин), занятие (20, 23, отдых), занятие (23, 24, сон).Сформулировать вопросы на Прологе: Когда бывает обед? Что бывает между 14 и 19 часами? Когда бывает сон? (сколько будет решений?)

Вариант 6.Построить базу данных “Важнейшие события Древнего Мира” на основе установленных фактов, произошедших с 31 по 6 век до нашей эры.

Каждый факт приводить в виде событие(Х,Y,Z), где X — название государства, где произошло событие, Y - в каком веке произошло событие, Z — какое произошло событие.

В 31-м веке до нашей эры возникли первые города-государства. Единое государство в Египте образовалось в 30 веке до нашей эры. В 27 веке до нашей эры в Индии появились первые древнейшие города, а в Египте построена пирамида Хеопса. Первые греческие государства появились в 18 веке до нашей эры. В этом же веке в Египте произошло крупное восстание бедняков и рабов. В 15 веке до нашей эры появились первые государства в Китае. Тутмос III правил в Египте в 15 веке до нашей эры. Греция вела троянскую войну в 13 веке до нашей эры. Вторжение борийских племен в Грецию произошло в 11 веке до нашей эры. В 8 веке до нашей эры был основан город Рим. Олимпийские игры стали проводиться в Греции в 8 веке до нашей эры. В 6 веке до нашей эры в Риме была установлена республика, а в Греции произошли реформы Солона. В этом же веке персы взяли Вавилон в Междуречье и завоевали Египет.

1. Составить 3 запроса к этой базе данных.

2. Какие события произошли в период с 15 до 7 в. до н.э.

3. В таблице даны некоторые характеристики движения планет Солнечной системы (числовые величины округлены):

Вариант 7

Таблица 6.

Характеристики движения планет солнечной системы

Планета	Расстояние до Солнца (у.е.)	Период обращения	Средние солнечные сутки
Меркурий	39	88 суток	176 суток
Венера	72	225 суток	117 суток
Земля	100	365 суток	24 часа
Марс	152	687 суток	25 часов
Юпитер	520	12 лет	10 часов
Сатурн	954	29 лет	10 часов
Уран	1920	84 года	24 часа
Нептун	3010	165 лет	22 часа
Плутон	3950	247 лет	6 суток

Составить базу данных, учитывая измерение по некоторым параметрам в разных единицах.

Ответить на вопросы: Какие планеты ближе к Солнцу, чем Земля? Какие планеты дальше от Солнца, чем Земля? На каких планетах солнечные сутки меньше, чем земные? На каких планетах период обращения измеряется в годах?

Вариант 8 Построить базу знаний “Рабочая смена”:

Мария работает в дневную смену. Сергей работает в вечернюю смену. Борис работает в вечернюю смену. Валентина работает в вечернюю смену. Два служащих знают друг друга, если они работают в одну смену. Определить: Знает ли Сергей Бориса? Кого знает Валентина? Кого знает Мария?

Вариант 9 Даны результаты сдачи экзаменов для группы из пяти учеников:

Таблица 7.

Успеваемость

Фамилия	Алгебра	Геометрия	История
Бобров	5	3	2
Вяткин	5	5	5
Кротов	2	3	3
Соснин	4	4	4
Вавилов	4	2	1

Построить базу знаний о результатах экзаменов, определив в ней следующие правила:

отличник - человек, у которого по всем предметам пятерки;

двоечник - есть хотя бы одна двойка;

математик - по алгебре и по геометрии учится на 4 и 5;

введите предикаты алгебра, геометрия, история для определения оценки Y для ученика X.

Получить ответы на следующие вопросы: Является ли Вяткин отличником? Определить всех отличников. Является ли Соснин математиком? Определить всех неуспевающих по истории.

Вариант 10. Сформировать базу знаний “Квартет” из следующих фактов и правил:

Мартышка играет на скрипке. Осел играет на альте. Козел играет на виолончели. Мишка играет на контрабасе. Четверо музыкантов X,Y,Z и W могут образовать квартет, если один из них играет на скрипке, другой — на альте, третий — на виолончели и четвертый — на контрабасе.

Ответить на вопросы: Кто играет на альте? На чем играет мартышка? Образуют ли квартет Мартышка, Осел, Козел и Мишка? Кто из музыкантов данной базы знаний может образовать квартет?

Вариант 11. База знаний “Воинская служба”:

возраст(борис ,18), возраст(андрей, 17), возраст(михаил,18), возраст(анна,18), возраст(юлия ,17), мужчина(андрей), мужчина(борис), мужчина(михаил), женщина(анна), женщина(юлия).

Определить правило подлежит призыву, не_подлежит_призыву.

Сформулировать вопросы: Кто подлежит призыву? Подлежит ли призыву Анна?

Вариант 12. База знаний "Семья”:

мать(екатерина, юлия), мать(екатерина, мария), мать(анна, екатерина), отец(петр, юлия), отец(виктор,петр), отец(андрей, екатерина).

Дополните базу данных предикатом мужчина, женщина. Определите правила дед, бабушка, внук, внучка, тетя, дядя.

Сформулировать вопросы на Прологе:

Кто является ребенком Екатерины и Петра? Кто является дедом Юлии? Кто является бабкой Юлии?

Вариант 13.Запрограммируйте утверждения.

Число четное. Число не четное. Ни одно число не является четным и нечетным одновременно. Число не четное, если следующее за ним четное. Число, следующее за данным числом нечетное, если данное число четное, число, следующее за данным числом четное, если данное число нечетное.

Рекомендуемая литература

1. Стобо Д.Ж. Язык программирования Пролог: Пер. с англ.- М.- Радио и связь, 1993.-368 с.:ил.

2. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

3. Информатика. Задачник-практикум в 2 т./Под ред. И.Г.Семакина, Е.К. Хеннера: Том.2.-М.:-БИНОМ. Лаборатория знаний, 2003.-278 с.:ил.

4. Каймин В.А. Основы компьютерной технологии.- М.:Финансы и статистика, 1992.-208 с.: ил.

Лабораторная работа №2. Арифметика. Управление логическим выводом в программах

Пример 1. Описать предикаты для вычисления суммы, разности, произведения, частного двух чисел, возведения числа в квадрат, вывода остатка при деление на 3, вывод случайного числа из интервала [1,100].

Программа 13. Арифметика

Domains

N=integer

R=real

Predicates

add(N,N)

sub(N,N,N)

multi(N,N,N)

division(N,N,R)

kvadrat(N,N)

ostat(N,N)

vivod(N)

Clauses

add(X,Y):-S=X+Y, write(“Sum= ”,S),nl.

sub(X,Y,S):-S=X-Y.

multi(X,Y,P):-P=X*Y.

division(X,Y,R):-Y<>0, R=X/Y.

kvadrat(X,N):-N=X*X.

ostat(X,N):-N=X mod 3.

vivod(N):-random(Y), N=1+Y*100.

Пример 2. Программирование взаимоисключающих утверждений. Процедуру нахождения наибольшего из двух чисел можно записать в виде отношения

max(X,Y,X):-X>=Y.

max(X,Y,Y):-X<Y.

Эти правила являются взаимоисключающими. Возможна более экономная формулировка: если X>=Y, то максимум=X, иначе =Y. На Прологе это запишется следующим образом:

max(X,Y,X):-X>=Y, !.

max(_,Y,Y).

Программа 14. Максимум

Domains

N=integer

Predicates

max(N,N,N)

Clauses

max(X, Y, X):-X>Y,!.

max(_,Y,Y).

Пример 3. Рассмотрим различные способы записи предиката different, определяющего различны ли числа, использующие сочетание встроенных предикатов ! и fail.

different(X,X):-!,fail.

different(_,_).

или

different(X,Y):-X=Y,!,fail.

different(_,_).

или

different(X,Y):-X=Y,!,fail; true.

/* true –встроенный предикат, который всегда истиннен*/

или

different(X,Y):-not(X=Y).

Задания для самостоятельной работы

№1. Описать предикаты:

1. Найти квадрат числа X; куб числа X.

2. Найти значение функций у = а*х + b, где a, b и х — целые числа.

3. Найти периметр треугольника, если все его стороны известны.

4. Найти площадь прямоугольного треугольника по двум его катетам

5. Найти площадь трапеции с основаниями А и В и высотой Н.

6. Найти квадрат гипотенузы в прямоугольном треугольнике по двум его катетам.

7. Найти объем прямоугольного параллелепипеда со сторонами А, В и С.

8. Зная скорость V и время Т, определите путь.

9. Найти последнюю цифру в записи натурального числа.

10. Найти цифры в десятичной записи двузначного натурального числа.

11. Найти первую цифру в десятичной записи трехзначного натурального числа.

12. Найти сумму цифр в десятичной записи трехзначного натурального числа.

№2.

1. Найти А. Наименьшее значение из двух чисел;

2. Найти Б. Наименьшее значение из трех чисел на основе первой задачи;

3. Найти В. Наименьшее значение из шести чисел на основе второй задачи.

4. Определить, удовлетворяют ли длины трех отрезков условию прямоугольного треугольника.

5. Определить, удовлетворяют ли длины трех отрезков условию треугольника.

6. Найти модуль числа X.

7. Описать предикат для вычисления функции, заданной соотношением:

Рекомендуемая литература

1. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

2. Информатика. Задачник-практикум в 2 т./Под ред. И.Г.Семакина, Е.К. Хеннера: Том.2.-М.:-БИНОМ. Лаборатория знаний, 2003.-278 с.:ил.

Лабораторная работа №3. Повторение и рекурсия

Пример 1. Выводить на экран квадрат числа, вводимого пользователем, пока не будет введен 0.

Программа 15. Вывод квадрата числа

Domains

x=integer

Predicates

repeat

check(x)

Clauses

repeat.

repeat:- repeat.

go:- repeat, write (“Введите число пожалуйста или 0-для выхода ”),

readint(A), check(A).

check(0):-nl,write(“ok”),!.

check(A):-B=A*A, write(B),nl, fail.

Или

go:- repeat, write (“Введите число ”), readint(A),

B=A*A, write(А, “^2= ” ,B),nl,

write(“прервать да/нет (y/n) ”), readchar(C), C= “n”,!.

Пример 2. Организовать меню для выбора арифметической операции.

Программа 16. Меню

Domains

x=integer

Predicates

actions(x)

repeat

Clauses

repeat.

repeat:- repeat.

menu:- repeat,

write(“Введите 1 для +, 2 для *, 3-для -, 0-для выхода\n”),

readint(N),

actions(N).

actions(0):-!.

actions(1):-write(“Введите первое число”), nl, readint(A),

write(“Введите второе число”) nl, readint(B),

С=A+B,write(C),nl,fail.

actions(2):- write(“Введите первое число”), nl, readint(A),

write(“Введите второе число”) nl, readint(B),

С=A*B,write(C),nl,fail.

actions(3):- write(“Введите первое число”), nl, readint(A),

write(“Введите второе число”) nl, readint(B),

С=A-B,write(C),nl,fail.

Пример 3. Вычислить n-ый член последовательности Фибоначчи. N-ый член последовательности Фибоначчи, начиная с третьего, определяется суммой 2-х предыдущих, а 1-ый и 2-ой члены равняются единице.

Введем двуместный предикат fib, первый аргумент будет определять порядковый номер члена, а второй будет записываться для записи ответа. Введем два факта, первый - первый член последовательности Фибоначчи равен 1, второй - второй член последовательности равен 1, а для определения n-го члена запишем правило. Действительно, чтобы определить n-ый член, мы должны определить значения двух предыдущих и сложить их.

fib(1,1).

fib(2,1).

fib(N,F):- N1=N-1, fib(N1,F1), N2=N-2, fib(N2,F2), F=F1+F2.

? fib(1,F)

Ответом будет F=1, и Пролог сделает попытку сопоставить с запросом второй факт и потерпит неудачу. Однако сопоставление головы третьего утверждения с запросом происходит успешно и осуществляется попытка доказать цель fib(-1,F1), что в свою очередь, приводит к цели fib(-2, …)и так далее, т.е. образуется бесконечный цикл. Эту ситуацию можно устранить, используя отсечение и тем самым, указывая Прологу, что не существует других решений в случае успешного согласования граничного условия.

Программа 17. Последовательность Фибоначчи

Domains

x=integer

Predicates

fib(x,x)

Clauses

fib(1,1):-!.

fib(2,1):-!.

fib(N,F):- N1=N-1, fib(N1,F1), N2=N-2, fib(N2,F2), F=F1+F2.

Задания для самостоятельной работы

1) Вычислить N!.

2) Вычислить n-ый член последовательности Фибоначчи.

3) Вывести все числа от n до 1.

4) Вывести все числа от 1 до n.

5) Вычислить сумму чисел от 1 до n.

6) Определите xⁿ, n>0.

7) Определите 2ⁿ, n>0.

8) Определите N⁵, n>0.

9) Вычислите сумму четных чисел от 1 до n.

10) Вычислите сумму квадратов нечетных чисел от 1 до n.

11) Вычислите сумму a_k, где a_k=1/(1+k).

12) Вычислить.

13) Вычислить.

14) Определите корень уравнения методом половинного деления.

15) Найти наибольший общий делитель двух чисел, трех чисел.

16) Определить число сочетаний .

17) Вычислить N!+(N-1)!+...+2!+1!.

18) Вычислить количество четных элементов на заданном интервале.

19) Перевести число из десятичной системы счисления в систему с основанием N, где N<10, N>1.

Рекомендуемая литература

1. Стобо Д.Ж. Язык программирования Пролог: Пер. с англ.- М.- Радио и связь, 1993.-368 с.:ил.

2. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

3. Информатика:Учеб.пособие для студ.пед.вузов/А.В.Могилев, Н.И.Пак, Е.К.Хеннер;Под ред. Е.К.Хеннера.-3-е изд., перераб. и доп.-М.:Издательский центр “Академия”, 2004.-848 с.

Лабораторная работа №4. Применение рекурсии для обработки списков

Пример 1. Определить количество элементов в списке.

Количество элементов пустого списка равно 0, в противном случае, нужно определить количество элементов в хвосте и найденное значение увеличить на единицу.

Программа 18. Определение длины списка

Domains

list = integer*

Predicates

length_of(list, integer)

Clauses

length_of([], 0):-!.

length_of([_|T], N) :- length_of(T, N1),N = N1 + 1.

?- length ([2, 12, 45]), X).

Ответ: Х=3.

Пример 2. Найти сумму элементов в списке.

Сумма элементов пустого списка равна 0, сумма элементов непустого списка определяется сложением головы списка с суммой элементов хвоста.

sum ([], 0):-!.

sum ([H|T], S) :- sum (T, S1), S = S1+H.

?-sum ([2, 12, 45]), X).

Ответ: Х=59

Пример 3. Определить принадлежность элемента списку.

Программа 19. Определение принадлежности элемента списку

Domains

type=integer

list=type*

Predicates

member(type,list)

Clauses

member(H,[H|_]):-!.

member(H,[_|T]):-member(H,T).

Запрос:

member (4,[1,3,4,9]).

Ответ: Yes.

Данная программа имеет очень простой декларативный смысл: элемент принадлежит списку, если он является его головой или принадлежит хвосту списка.

Пример 4. Объединить два списка.

Эту задачу можно описать с помощью следующих предикатов:

а) если к пустому списку [] добавить список Р, то в результате получится Р;

б) чтобы добавить список Р к концу списка [X|Y], нужно Р добавить к хвосту Y и затем присоединить к голове Х, при этом получается список [Х|Т].

Программа 20. Объединение двух списков

Domains

type=integer

list=type*

Predicates

append(list,list,list)

Clauses

append([],L,L):-!.

append([H|T],P,[H|Y]):-append(T,P,Y).

? append ([3, 5, 7], [12,5],K).

Ответ: К=[3,5,7,12,5]

Процедуру append можно использовать:

1) для разбиения списка на подсписки:

? append (X,Y,[1,2])

Ответ: X=[ ]Y=[l,2]

X=[l] Y=[2]

X=[l,2] Y=[]

2) Для вывода последнего элемента списка:

last(X,L):-append(_,[X],L)

Пример 5. Удаление элементов из списка.

Первый аргумент указывает удаляемый элемент, второй аргумент - исходный список и третий - список-результат.

Программа 21. Удаление элементов из списка

Domains

type=integer

list=type*

Predicates

delete(type,list,list)

Clauses

delete(X,[X|T],T):-!.

delete(X,[Y|T],[Y|T1]):-delete(X,T,T1).

Смысл: результат удаления произвольного элемента из пустого списка, есть пустой список, если удаляемый элемент совпадает с головой списка, то результатом программы является хвост списка, иначе удаление производится из хвоста списка.

Данная программа удаляет первое вхождение элемента в список. Знак отсечения "!" в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.

Для удаления всех вхождений элемента Х программу надо дополнить:

delete(_, [], []) :-!.

delete(X, [X | T], W) :- delete(X, T, W),!.

delete(X, [Y | T], [Y|W]) :- delete(X, T, W) .

Смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, а затем удалять его из хвоста, иначе надо сразу удалять элемент из хвоста.

Пример 6. Индексация элементов списка.

Определить номер элемента X.

nomer([X |_], 1, X):-!.

nomer ([_| T], N, X) :- nomer(T, N1, X), N=N1+1.

Пример 7. Вывести максимальный элемент.

max ( [X] , X) .

max ([X | T], X) :- max (T, M), X>M, !.

max ( [_| T] , M) :- max (T, M) .

Смысл программы: если в списке один элемент - он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста.

Пример 8. Обращение списка.

Обратить список из одного элемента - означает оставить список без изменения. Обратить более длинный список - обратить его хвост, а потом справа добавить к нему голову исходного списка.

reverse([X], [X]):-!.

reverse ([X | T], Z) :- reverse (T, W), append(W, [X], Z).

Пример 9. Иногда бывает полезно представить в виде списка информацию, содержащуюся в известных фактах. В Прологе для этой цели служит предикат findall. Полный формат предиката: findall(Переменная, Атом, Список), здесь Атом- отношения, которое определяет список элементов, конкретизирующих переменную в качестве аргумента предиката атом. Рассмотрим предикат на примере вычисления общей суммы окладов служащих

Прорамма 22. Сумма окладов служащих

Domains

i=integer

sp=i*

fam,im,dolgnost=symbol

Predicates

sum(sp,i)

spisok(fam,im,dolgnost,i)

Clauses

sum([],0):-!.

sum([H|T],S):-sum(T,S1),S=S1+H.

spisok(ivanov, ivan, slesar,400).

spisok(petrov, petr,tokar,200).

spisok(sidorov, denis,plotnik,100).

go:-findall(X,spisok(_,_,_,X),L), sum(L,A).

Задания для самостоятельной работы

1) Определите количество элементов в списке.

2) Определите сумму элементов списка

3) Определите количество нечетных элементов в списке.

4) Определите, принадлежит ли заданный элемент списку.

5) Определите, сколько раз заданный элемент входит в список.

6) Выведите максимальный элемент.

7) Выведите голову списка.

8) Выведите последний элемент.

9) Замените голову списка.

10) Определите номер элемента X.

11) Выведите элемент под номером N.

12) Удалите из списка все вхождения заданного элемента.

13) Объедините два списка.

14) Перепишите список в обратном порядке.

15) Объедините два списка без дублирования элементов.

16) Удалите первое вхождение заданного элемента.

17) Сложить поэлементно 2 списка.

18) Сложить два списка следующим образом: a₁+b_n, a₂+b_n_-1, ...,a_n_-1+b₂, a_n+b₁.

19) Найти количество элементов, предшествующих первому(последнему) максимальному.

20) Переместите голову списка в конец списка.

21) Найти сумму максимального и минимального элементов списка.

22) Поменяйте местами элементы с нечетными индексами с элементами с четными индексами.

23) Составить список из цифр заданного числа в обратном порядке. Например, 127645: [5,4,6,7,2,1].

24) Выполните N последовательных перестановок головы в конец списка.

25) Увеличьте каждый элемент списка на заданный элемент.

26) Увеличьте элемент с заданным номером на заданное число.

27) Все вхождения заданного элемента уменьшите на заданное число.

28) Удалите элемент с заданным номером N.

29) Создать список, элементами которого являются 2ⁿ, n!, члены последовательности Фибоначчи.

30) Определите среднее элементов списка.

31) Замените четные элементы списка нулем.

32) Определите сумму элементов, больше заданного N.

33) Отсортируйте список методом пузырька.

34) Отсортируйте список методом вставками.

35) Отсортируйте список быстрым методом сортировки.

36) Используя предикат findall, решите следующие задачи:

1. Вывести самых молодых жильцов дома и номера квартир, в которых они живут.

2. Вывести фамилии студентов и их возраст с максимальным размером стипендии.

3. Вывести фамилии сотрудников предприятия и их оклады, оклады которых меньше среднего.

4. Вывести студентов с заданной фамилией и посчитать их количество.

Рекомендуемая литература

1. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

2. Практикум по логическому программированию: Методические рекомендации для студентов и преподавателей по лабораторному практикуму по курсу «Логическое программирование»/ Сост. Р.И. Баженов, И.И. Раскина. – Омск: Изд-во ОГПУ, 1995. – 85 с.

Лабораторная работа №5. Решение логических задач.

Пример 1. Беседует трое друзей: Белокуров, Рыжов, Чернов. Брюнет сказал Белокурову: “Любопытно, что один из нас блондин, другой брюнет, третий - рыжий, но ни у кого цвет волос не соответствует фамилии”. Какой цвет волос у каждого из друзей?

Для решения построим вспомогательную таблицу:

Таблица 8.

Вспомогательная таблица соответствия

_Цвет ^{Фамилия}	Белокуров	Рыжов	Чернов
блондин	-
рыжий		-
брюнет	-		-

Выводы:

1) Белокуров не брюнет и не блондин;

2) Чернов не черный, цвет волос Чернова и Белокурова не совпадают;

3) Рыжов не рыжий, цвет волос у Рыжова и Белокурова, Рыжова и Чернова не совпадают.

Программа 23. Логическая задача на соответствие

Predicates

fam(symbol)

color(symbol)

cootvet(symbol, symbol)

Clauses

fam(belokurov).

fam(ryzov).

fam(chernov).

color(ryziy).

color(cherniy).

color(beliy).

cootvet(X,Y):- fam(X), color(Y), X=belokurov,

not(Y=cherniy), not(Y=beliy).

cootvet(X,Y):- fam(X), color(Y), X= chernov,

not(Y=cherniy),not(cootvet(belokurov,Y).

cootvet(X,Y):- fam(X), color(Y), X= ryzov,

not(cootvet(belokurov, Y), not(cootvet(chernov, Y).

Пример 2. На скамейке сидели Петя, Боря, Коля. Петя справа от Бори, Боря справа от Коли. Кто сидел посередине? Кто сидел с правого(левого) края? Кто сидел между указанными объектами(увеличьте число объектов)?

Программа 24. Логическая задача на выяснение порядка

Predicates

rayd(symbol, symbol, symbol)

sprava(symbol, symbol)

seredina(symbol

kr_cl(symbol)

kr_cpr(symbol)

Clauses

sprava(kolya, boray). /*Справа от Коли Боря*/

sprava(boray, petay).

rayd(X,Y,Z):- sprava(X,Y), sprava(Y, Z).

seredina(X):- rayd(_,X,_).

kr_cl(X):- rayd(X,_,_).

kr_cpr(X):- rayd(_,_,X).

Задания для самостоятельной работы

1) Коля и Саша носят фамилии Шилов и Гвоздев. Какую фамилию носит каждый из них, если Саша с Шиловым живут в разных домах.

2) В соревнованиях по бегу Юра, Гриша и Толя заняли три первых места. Какое место занял каждый ребенок, если Гриша занял не второе и не третье место, а Толя не третье?

3) Три подруги вышли в белом, зеленом и синем платьях и туфлях. Известно, что только у Ани цвета платья и туфлей совпадали. Ни туфли, ни платье Вали не были белыми. Наташа была в зеленых туфлях. Определить цвета платья и туфель на каждой из подруг.

4) На заводе работали три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Иванов и Семенов. У слесаря нет ни братьев, ни сестер. Он самый младший из друзей. Семенов, женатый на сестре Борисова, старше токаря. Назвать фамилии слесаря, токаря и сварщика.

5) В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом находится между кувшином и сосудом с квасом, в банке - не лимонад и не вода. Стакан находится около банки и сосуда с молоком. Как распределены эти жидкости по сосудам.

6) Воронов, Павлов, Левицкий и Сахаров – четыре талантливых молодых человека. Один из них танцор, другой художник, третий-певец, а четвертый-писатель. О них известно следующее: Воронов и Левицкий сидели в зале консерватории в тот вечер, когда певец дебютировал в сольном концерте. Павлов и писатель вместе позировали художнику. Писатель написал биографическую повесть о Сахарове и собирается написать о Воронове. Воронов никогда не слышал о Левицком. Кто чем занимается?

7) Три друга заняли первое, второе, третье места в соревнованиях универсиады. Друзья разной национальности, зовут их по-разному, и любят они разные виды спорта. Майкл предпочитает баскетбол и играет лучше, чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место. Кто является австралийцем? Каким спортом увлекается Ричард?

8) Три девочки Маша, Рита, Лена пошли гулять. На улице было жарко, и они купили мороженое «Белка», «Стрелка», «Гагара». Какое мороженое купила каждая из девочек, если Лена купила не «Белку» и не «Гагару», а Рита – не «Гагару».

9) В комнате находятся Коля, Света, Оля. Каждый из них сидит на отдельной мебели (кровать, стул, диван). Известно, что Коля сидит не на стуле и не на кровати. Света не сидит на стуле. Кто где сидит?

10) На столе лежат ручка, карандаш, фломастер, красного, синего и зеленого цвета. Известно, что ручка лежит между предметом красного и зеленого цвета. Карандаш либо зеленый, либо синий.

11) Однажды в Артеке за круглым столом оказалось пятеро ребят из Москвы, Санкт-Петербурга, Новгорода, Перми, Томска: Денис, Игорь, Иван, Алеша, Сергей. Москвич сидел между томичем и Сергеем, санкт-петербуржец - между Денисом и Игорем, а напротив него сидел пермяк и Иван. Алеша ни разу не был в Санкт-Петербурге, а Денис не бывал в Москве и Томске, а томич с Игорем регулярно переписываются. Определите, кто в каком городе живет каждый из ребят.

12) На улице, встав в кружок, беседует четыре девочки: Аня, Валя, Надя, Галя. Девочка в зеленом платье – не Аня и не Валя - стоит между девочкой в голубом платье и Галей. Девочка в белом платье стоит между девочкой в розовом платье и Валей. Какого цвета платье у каждой из девочек?

13) Трое юношей: Коля, Дима и Юра влюблены в трех девушек: Аню, Лену, Вику. Но эта любовь без взаимности. Коля любит девушку, влюбленную в юношу, который любит Лену. Дима любит девушку, влюбленную в юношу, который любит Вику. Лена не любит Юру.

14) Составить базу знаний по сказке “Репка”. Фактами в этой базе должны быть утверждения типа тянет(X,Y). Составить правила, определяющие: кто первый тянет репку, кто последний тянет реку, кто тянет после бабки, кто тянет на четвертом месте.

15) Даны числа X, Y, Z, T. X меньше Yи меньше T; Y больше Z и больше T; Z больше X и меньше T. В каком порядке расположены эти числа.

16) На одной yлице стоят 5 домов, окpашенных в 5 pазных цветов. В каждом доме живет гpажданин дpyгой стpаны. Каждый из них пьёт свой напиток, курит свои сигареты и содержит своё домашнее животное. Определите, кто из них содержит рыб? Британец живёт в красном доме. У шведа есть собака. Датчанин пьёт чай. Зелёный дом стоит слева от белого и вплотную к немy. Хозяин зелёного дома пьёт кофе. У того, кто курит Pall-Mall, есть птицы. Хозяин желтого дома курит Dunhills. Хозяин среднего дома пьёт молоко. Норвежец живёт в пеpвом доме. Человек, который курит Blends, живёт рядом с хозяином котов. Тот, кто содержит лошадей, живёт pядом с тем, кто кypит Dunhills. Тот, кто курит Blue Master, пьёт пиво. Hемец кypит Prince. Норвежец живёт рядом с синим домом. У того, кто курит Blends, есть сосед, который пьёт водy.

Рекомендуемая литература

1. Информатика. Задачник-практикум в 2 т./Под ред. И.Г.Семакина, Е.К. Хеннера: Том.2.-М.:-БИНОМ. Лаборатория знаний, 2003.-278 с.:ил.

Лабораторная работа №6. Головоломки. Игровые программы.

Пример 1. Нарисовать конверт, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии. Введем обозначения, ребра – латинскими буквами, вершины - цифрами.

Знания о структуре графа можно представить следующим образом: rebro(a,1,2), rebro(a,2,1), rebro(b,2,3), rebro(b,3,2), rebro(c,1,3), rebro(c,1,2), rebro(c,3,1), rebro(d,2,4), rebro(d,4,2), rebro(e,2,5), rebro(e,5,2), rebro(f,3,4), rebro(f,4,3), rebro(g,3,5), rebro(g,5,3), rebro(h,4,5), rebro(h,5,4).

Решением задачи должен явиться список пройденных ребер графа, причем длина его должна быть равна 8, и в нем не должно быть повторяющихся ребер, что можно описать так:

prohod(T,P):-length(P,8),write_list(P),!.

prohod(T,P):-rebro(R,T,H), not(member(R,P), prohod(H,[R|P).

T-текущая вершина графа, а P-список пройденных ребер. Первое правило означает, что если длина списка P пройденных вершин становится равной 8, то список P выводится на печать. Это правило ограничивает рекурсивный перебор вершин и ребер, проводимый вторым правилом. Второе правило является генератором перебора, оно перебирает предикаты “rebro()” и находит такое ребро R, из текущей вершины Т в новую H, чтобы оно не принадлежало списку P, зато это ребро добавляется в качестве головы к списку P, и поиск дальнейшего пути производится уже из новой вершины H.

Пример 2. Программа “Угадай число”.

Программа 25. Логическая игра «Угадай число»

Predicates

play_the_game

give_info

play_it

generate_rand(integer)

play_it_sam(integer)

test_and_tell(integer,integer)

say_you_got_it_right(integer)

say_too_big

say_too_small

Clauses

play_the_game:-give_info, play_it.

/*информация для пользователя*/

give_info:-makewindow(1,7,7,"",0,0,25,80),

makewindow(2,7,7,"Угадай число", 2,20,22,45),

nl, write("Это игра Угадай число"),

nl, write("Я загадаю число из"),

nl, write("интервала [1,100]"),

nl, write("Я буду подсказывать больше"),

nl, write("или меньше задуманное число"),nl,

nl, write("Кода будешь готов- нажми space bar"),

nl,readchar(_),

clearwindow.

/*выполнение игры*/

play_it:-generate_rand(A),

play_it_sam(A).

/*генерация случайного числа*/

generate_rand(X):-

random(R),

X=1+R*100,

nl,write("Я загадал число"),

nl,write("Теперь дело за Вами"),nl.

/*запрос к пользователю */

play_it_sam(X):-

nl, write ("Введите свой вариант"),

nl, readint(G),

test_and_tell(X,G),

play_it_sam(X).

/* проверка и выдача результата*/

test_and_tell(X,X):- say_you_got_it_right(X),!.

test_and_tell(X,Y):- X>Y, say_too_big,!.

test_and_tell(_,_):- say_too_small.

/*выдача сообщений*/

say_too_big:-nl, write("Загаданное число больше").

say_too_small:-nl, write("Загаданное число меньше").

say_you_got_it_right(X):-nl, write("Вы правы"),

nl,write("Я загадал ",X),

nl, write("До новых встреч!"),

nl, write("Нажмите space bar"),

nl,readchar(_),

exit.

Goal

play_the_game.

Пример 3. Игра Баше – 23 спички. На столе 23 спички, 2 игрока по очереди берут от 1 до 3 спичек, проигравшим считается тот, кто возьмет последнюю спичку.

Программа 26. Логическая игра «Игра Баше – 23 спички»

Predicates

play_the_game

do_windows

play(integer,integer,integer)

play_it_again(integer,integer,integer)

real_int(real,integer)

Clauses

play_the_game:-do_windows,play(23,0,0).

/*правило для образования окон*/

do_windows:-makewindow(1,7,7,"",0,0,25,80),

makewindow(2,7,7,"Игра 23 спички", 1,5,22,40),

nl, write("Добро пожаловать!"),

M=23, H=0, C=0,

nl, write("Всего ",M," спички" ),

nl, write("По очереди мы будем перемещать " ),

nl, write("спички в свои кучки"),

nl, write("За раз можно взять 1, 2, 3 спички"),nl,

nl, write("Проиграет, тот кто заберет последнюю спичку"),

nl, write("Итак, начнем, всего ", M, "сп."),nl,

nl, write("я взял ",C," сп. Вы взяли ",H, " сп."),nl.

play(M,H,C):-play_it_again(M,H,C).

/*правило определения победителя*/

play_it_again(M,_,_):-

M<=0,

nl, write("Вы выиграли!"),

nl, write("Нажмите любую клавишу для выхода"),

readchar(_), clearwindow,!,exit.

play_it_again(1,_,_):-

nl, write("Я выиграл!"),

nl, write("Нажмите любую клавишу для выхода"),

readchar(_), clearwindow,!,exit.

play_it_again(M,_,_):-

nl, write("Ваш ход"),

nl, write("Сколько спичек вы хотите взять?"),

readint(Hn),

M2=M-Hn, H2=Hn,

write("Осталось ",M2,"сп."),

nl,write("Мой ход"),

random(F), Rea=1+3*F,

real_int(Rea,Rint),

M3=M2-Rint,

nl, write("Я беру ",Rint," сп."),

nl, write("Осталось ",M3, " сп."),nl,

M7=M3,H7=H2,C7=Rint,

play_it_again(M7,H7,C7).

/*вспомогательное правило*/

real_int(Re,In):-In=trunc(Re).

Goal

play_the_game

Задания для самостоятельной работы

1) Отгадать число, загаданное компьютером, максимум за 3 попытки.

2) 23 спички. Разработать выигрышную стратегию для компьютера.

3) Имеется два сосуда – на 3 и 5 литров. Как отмерить с их помощью 4 литра воды?

4) Решите задачу о перевозке фермером через реку волка, козы, капусты.

5) Раскрасить плоскую карту так, чтобы никакие две смежные области на ней не были раскрашены в одинаковый цвет. В наборе 4 цвета.

Таблица 9.

Поле для раскраски

a
b	c		d
e		f

6) Лабиринт задан матрицей соединений, в которой для каждой пары комнат указано, соединены ли они коридором. Построить путь перехода из комнаты “a” в комнату “g”:

Таблица 10.

Поле для лабиринта

	A	B	C	D	E	F	G
A	-	1	0	0	0	0	0
B	1	-	1	0	1	0	0
C	0	1	-	1	0	0	0
D	0	0	1	-	1	0	0
E	0	1	0	1	-	0	0
F	0	0	0	0	1	0	0
G	0	0	0	0	1	0	-

7) Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей n*n, элемент aij<0, если между городами дороги нет, в противном случае равен расстоянию между городами.

8) Задан лабиринт. Напишите программу для нахождения маршрутов для выхода из этого лабиринта. Начало маршрута точка О. Закрашенная клетка – стена.

Таблица 11.



		О

9) Быки и коровы. Игрок A выбирает секретный код, представляющий последовательность из N различных десятичных цифр (N=4). Игрок пытается угадать задуманный код и спрашивает игрока А о числе “быков” (“быки” - количество совпадающих цифр в одинаковых позициях предполагаемого и задуманного кодов; число “коров”- количество совпадающих цифр, входящих в предполагаемый и задуманный код, но находящиеся на разных позициях).

Тема: решение логических головоломок

Вариант №1

Три друга заняли первое, второе и третье места на школьной олимпиаде. Друзья учатся в разных классах, зовут их по-разному, и они участвовали в олимпиадах по разным предметам. Алексей участвовал в олимпиаде по химии, и он выступил лучше, чем девятиклассник. Семиклассник Сергей выступил лучше участника олимпиады по физике. Участник олимпиады по математике занял первое место. Кто из них в каком классе учится и кто в какой олимпиаде участвовал?

Вариант №2

Трое хищников – волк, медведь и лиса пошли на охоту. У них разный возраст и они охотились на разную дичь. Медведь любит рыбу и поймал дичи больше, чем тот, кому 2 года. Трехлетний волк поймал больше, чем любитель зайцев. Тот, кто любит кур, поймал больше всех. Одному из них 4 года. Определите, у кого какой возраст и кто какую дичь предпочитает.

Вариант №3

Три друга – Иван, Дмитрий и Степан преподают биологию, физику и химию в школах Москвы, Санкт-Петербурга и Киева. Иван – не в Москве, Дмитрий – не в Санкт-Петербурге. Москвич не преподаёт физику. Тот, кто живёт в Санкт-Петербурге, преподаёт химию. Дмитрий не преподаёт биологию. Кто в каком городе живёт и что преподаёт?

Вариант №4

Три ученика – Коля, Миша и Андрей сидят в классе за партами первого ряда. У них разный цвет волос и они любят разные предметы. Миша любит физику и сидит ближе к классной доске, чем рыжий. Блондин Коля сидит ближе к классной доске, чем любитель литературы. Тот, кто любит математику, сидит за первой партой. Один из них брюнет. Определите, у кого какой цвет волос, и кто какой предмет предпочитает.

Вариант №5

Три друга заняли первое, второе и третье места в соревнованиях универсиады. Друзья разной национальности, зовут их по-разному, и любят они разные виды спорта. Майкл предпочитает баскетбол и играет лучше, чем американец. Израильтянин Саймон играет лучше теннисиста. Игрок в крикет занял первое место. Кто из них австралиец? Каким видом спорта увлекается Ричард?

Вариант №6

Кондратьев, Давыдов и Фёдоров живут на одной улице. Один из них - столяр, другой – маляр, третий – водопроводчик. У столяра самый большой дом из троих и у него нет автомобиля. Федорову нравится машина Кондратьева и его дом меньше, чем у маляра. Определите, кто чем занимается, у кого есть машина.

Вариант №7

Браун, Гриффит, Клеменс и Грин - четверо студентов университетов разных стран приехали на международный фестиваль молодёжи и студентов. Один из них – канадец, второй – американец, третий – англичанин, четвёртый – австралиец. Браун и Клеменс были на концерте, в котором принимал участие их знакомый англичанин. Гриффит и австралиец знакомы, так как пели дуэтом под аккомпанемент их знакомого американца. Австралиец пригласил к себе в гости своего знакомого Грина и собирается пригласить своего знакомого Брауна. Определите национальности студентов.

Вариант №8

В одном театре работают четыре актёра: Смирнов, Снегов, Морев и Никитин. Один из них играет роль Отелло, другой – короля Лира, третий – Ромео, четвёртый – Гамлета. Смирнов – не Отелло и не Гамлет. Морев – не Ромео и не Отелло. Никитин – не Гамлет, не Отелло. Снегов не играет ни Гамлета, ни Ромео. Если Морев играет Гамлета, то Смирнов не играет короля Лира. Кто из актёров кого играет?

Вариант №9

Пол, Джон и Джордж – три музыканта. Один из них – гитарист, другой – ударник, третий – пианист. Каждый из них выступает в составе одной из рок-групп - «Ромашка», «Василёк» или «Колокольчик». Тот, кто выступает в составе «Ромашки», не гитарист. Джон выступает в составе не «Василька». Пол – выступает в составе не «Ромашки». Ударник выступает в составе рок-группы «Василёк». Джон не пианист. На каком инструменте играет каждый из трёх музыкантов и в составе какой рок-группы выступает?

Вариант №10

Лена, Коля, Марина и Саша работают на одном предприятии конструктором, технологом, экономистом и дизайнером. Лена и Марина учились вместе с экономистом. Коля и дизайнер в обеденный перерыв часто играют в теннис с технологом. Дизайнер постоянно сталкивается по работе с Леной и иногда с Сашей. Кто кем работает?

Вариант №11

Трое мальчиков Костя, Фома и Марат дружили с тремя девочками – Женей, Светой и Мариной. Но вскоре компания разделилась на пары, потому что оказалось, что Света ненавидит ходить на лыжах. Костя, Женин брат, часто катается со своей подружкой на лыжах. А Фома бежит на свидание к Костиной сестре. С кем же проводит время Марат?

Вариант №12

В комнате женского общежития живут четыре девушки: Мира, Мона, Мод и Мэри. Как-то раз они собрались все вместе, причём каждая занималась своим делом. Одна делала маникюр, другая – расчёсывала волосы, третья – прихорашивалась перед зеркалом, а четвёртая – читала. Точно о них известно следующее: Мира не делала маникюр и не читала. Мод не прихорашивалась перед зеркалом и не делала маникюр. Мэри не читала и не занималась маникюром. Мона не читала и не прихорашивалась перед зеркалом. Если Мод читала, то Мэри прихорашивалась перед зеркалом. Кто из девушек делала маникюр, кто расчёсывала волосы, кто прихорашивалась перед зеркалом, а кто читала?

Вариант №13

«Динамо», «Торпедо» и «Спартак» - команды-участники розыгрыша кубка по футболу из Челябинска, Краснодара и Самары. Команда из Челябинска забила меньше всех мячей. «Динамо» забила мячей больше, чем команда из Краснодара, а «Торпедо» меньше «Спартака». За какие города выступают названные команды?

Вариант №14

В одном купе поезда ехали три пассажира – мистер Джонс, мистер Смит и мистер Робинсон. Один из них житель Чикаго, другой живёт в Детройте, третий – в Окленде. За разговорами выяснилось, что мистер Джонс из Чикаго старше, чем тот, у кого нет детей. Житель Детройта самый старый. Мистер Смит, у которого двое детей, старше, чем житель Окленда. У одного из них только один ребенок. Определите, кто из какого города и у кого сколько детей.

Вариант №15

Билл, Джон и Ричард играют в одном оркестре. Они владеют разными музыкальными инструментами и выступают в костюмах разных цветов. Джон играет на саксофоне и находится ближе к дирижёру, чем тот, кто выступает в белом костюме. Билл на концерт одевает чёрный костюм и сидит ближе к дирижёру, чем флейтист. Альтист сидит к дирижёру ближе всех. Один из друзей приходит на концерт в костюме синего цвета. Определите, кто какими инструментами владеет и в каком костюме выступает.

Вариант №16

Петров, Семёнов и Арбузов – пилот, штурман и бортинженер. Один из них летает на самолёте ТУ-134, другой на АН-24, третий на ИЛ-76. Тот, кто летает на ТУ-134, не штурман. Семёнов работает не на АН-24. Петров – не на ТУ-134. Бортинженер летает на АН-24. Семёнов не пилот. У кого какая профессия и какой самолёт?

Вариант №17

Андреев, Борисов и Николаев – поэт, композитор и художник. У поэта нет бороды и он зарабатывает меньше всех. Андреев считает, что Николаеву очень идет борода. Андреев зарабатывает больше композитора. Определите, кто является поэтом, кто композитором, кто художником и у кого есть борода.

Вариант №18

За столиком в кафе познакомились три девушки: Алёна, Светлана и Марианна. Одна из них работает парикмахером в Салоне красоты, другая – модельером в Доме Мод, третья – медсестрой в санатории. Также выяснилось, что парикмахер – самая молодая из троих, Марианна старше модельера, а Светлана младше Алёны. Определите профессии девушек.

Вариант №19

В одном институте учатся три друга – Липатов, Кондратьев и Зайцев. Один из них будущий физик, второй – математик, третий – программист. У физика нет ни братьев, ни сестёр. Он самый младший из друзей. Зайцеву нравится сестра Липатова и он старше математика. Определите будущие профессии друзей.

Вариант №20

У Васи, Вани, Славы и Вовы живут дома собака, кошка, морская свинка и попугай. Вася и Слава знакомы с хозяином кошки. Ваня и хозяин собаки часто ходят в кино с хозяином попугая. Хозяин собаки постоянно встречается в школе с Васей и иногда с Вовой. У кого какое животное?

Вариант №21

Трое коллег – Костя, Митя и Артем пошли в ресторан. У них разное семейное положение и они любят разные блюда. Митя любит рыбу и получает больше, чем тот, кто холостой. Разведенный Костя получает больше, чем любитель пельменей. Тот, кто любит плов, получает больше всех. Один из них женат. Определите, у кого какое семейное положение, и кто какое блюдо предпочитает.

Вариант №22

В книжный магазин пришли четыре подруги: Соколова, Ястребова, Орлова и Голубева. Одна из них искала книгу «Поющие в терновнике», другая – «Финансиста», третья – «Охоту на овец», четвёртая – «Заводной апельсин». Соколова не искала книги «Поющие в терновнике» и «Заводной апельсин». Орлова – не искала книги «Охота на овец» и «Поющие в терновнике». Голубева не искала книги «Заводной апельсин» и «Поющие в терновнике». Если Ястребова искала книгу «Поющие в терновнике», то Голубева искала книгу «Финансист». Ястребова не искала книги «Заводной апельсин» и «Охота на овец». Какая девушка какую книгу искала?

Вариант №23

Боб, Джек и Рональд часто ходят в кино. Они любят разные жанры и предпочитают разные кинотеатры. Джек любит комедии и садится ближе, чем тот, кто ходит в кинотеатр «Звезда». Боб ходит в кинотеатр «Самара» и сидит ближе, чем любитель триллеров. Тот, кто любит боевики, сидит к экрану ближе всех. Один из друзей ходит в кинотеатр «Огонек». Определите, кто какой жанр любит и в какой кинотеатр предпочитает ходить.

Вариант №24

Кукушкина, Петухова и Галкина – модельер, менеджер и страховой агент. Одна из них водит форд, другая рено, третья ауди. Тот, кто ездит на форде, не менеджер. Петухова ездит не на рено. Кукушкина – не на форде. Страховой агент ездит на рено. Петухова не модельер. У кого какая профессия и какой автомобиль?

Вариант №25

Три семейные пары– Ивановы, Петровы и Сидоровы купили путевки за 2000$, 3000$ и 5000$ в Турцию, Италию и Испанию. Ивановы поехали не в Турцию, Петровы – не в Италию. Те, кто поехали в Турцию, не платили за путевку 5000$. Те, кто поехали в Италию, заплатили 3000$. Петровы не платили за путевку 2000$. Кто в какой стране отдыхал и кто сколько заплатил за путевку?

Вариант №26

«Тройка» думает, что «Туз» не в своём уме. «Четвёрка» думает, что «Тройка» и «Двойка» обе не могут быть не в своём уме. «Пятёрка» думает, что «Туз» и «Четвёрка» либо оба не в своём уме, либо оба в своём уме. «Шестёрка» думает, что «Туз» и «Двойка» оба в своём уме. «Семёрка» думает, что «Пятёрка» не в своём уме. «Валет» думает, что «Шестёрка» и «Семёрка» обе не могут быть не в своём уме. В своём ли уме «Валет»?

Вариант №27

Король думает, что королева думает, что она не в своём уме. В своём ли уме король?

Вариант №28

Антон, Максим и Дима учатся в художественной школе. Каждый ученик художественной школы рисует или портреты, или пейзажи, или натюрморты и у каждого ученика один любимый художник - И.Репин, И.Шишкин или А.Рублёв. Антон рисует портреты и учится лучше, чем тот, кто любит И.Репина. Максим любит И.Шишкина и учится лучше, чем тот, кто рисует пейзажи. Тот, кто рисует натюрморты, учится лучше всех. Один из учеников любит А.Рублёва. Определите, кто из учеников художественной школы что рисует и у кого какой любимый художник.

Вариант №29

На экскурсию в Эрмитаж приехали трое туристов – Кузнецов, Смирнов и Попов. Один из них из Казани, другой – из Самары, третий – из Москвы. Выяснилось, что житель Казани купил билет самым первым из троих. Кузнецов из Самары купил билет раньше, чем тот, кто живет в гостинице №1. Смирнов, живущий в гостинице №2, купил билет раньше, чем москвич. Один из них живет в гостинице №3.

Определите, кто из какого города и кто в какой гостинице живет.

Вариант №30

Тони, Майкл и Джон – спортсмены. Один из них боксер, второй футболист, третий – пловец. Один из них любит снег, второй любит дождь, третий любит солнечную погоду. Тот, кто любит солнечную погоду, не боксер. Тони не любит снег. Майкл – не любит солнечную погоду. Футболист любит снег. Тони не пловец. У кого какая любимая погода и кто каким спортом занимается?

Рекомендуемая литература

1. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

2. Информатика:Учеб.пособие для студ.пед.вузов/А.В.Могилев, Н.И.Пак, Е.К.Хеннер;Под ред. Е.К.Хеннера.-3-е изд., перераб. и доп.-М.:Издательский центр “Академия”, 2004.-848 с.

Лабораторная работа №7. Обработка файлов. Предикаты для работы с файлами

deletefile(DOS_filename)-удаление файла

save(DOS_filename) –сохранение файла

renamefile(old_DOS_filename, new_DOS_filename)-переименовыфвание файла

existfile(DOS_filename)-проверка на наличие файла с таким именем

flush(file_domain)-сброс данных из внутреннего буфера, отведенного для данного устройства записи

disk(Path) –выбор дисковода и пути доступа

dir(Path, File_spec, File_name) –Переменой Path должен быть присвоен корректный путь доступа, переменная File_spec задает расширение представляющей интерес группы файлов. Данный предикат выдает каталог имен файлов с заданным расширением; вы можете выбрать среди них нужный и нажать Enter. Имя файла будет присвоено переменой File_name.

При описании файловых доменов тип домена записывается по левую сторону от знака равенства, а имя доомена по правую.

Пример:

file=datafile

file=datafile1;datafile2

openwrite(datafile,filename) - открытие файла для записи или создание, где datafile- введеннный пользователем файловый домен, filename-имя файла в DOS, теперь ссылки на datafile будут означать обращение к filename.

writedevice(datafile) -назначение файла в качестве устройства записи

openread(datafile,filename) - открытие файла для чтения.

readdevice(datafile) -назначение файла устройством чтения

openmodify(datafile,filename) - открытие файла для редактирования, указатель помещается в начало файла, сместить указатель можно при помощи предиката filepos.

openappend(datafile,filename) - открытие файла для добавления данных в конец файла.

closefile(datafile) -закрытие файла

Рассмотрим примеры работы с файлами.

Пример 1. Вывести информацию на экран дисплея и в файл на диске.

Программа 27. Запись данных в файл

Domains

str = string

file = datafile

Predicates

data(str)

write_lines

Goal

openwrite(datafle,"file1.dat"),

write_lines,

closefile(datafile).

Clauses

data("Старому году оставьте печали,!").

data("Забудьте обиду, беду.").

data("Только успехов, здоровья и счастья,").

data("Мы Вам желаем в Новом году!").

write_lines:-

data(Line),

write(" ",Line),nl,

writedevice(datafile),

write(" ",Line),nl,

writedevice(screen), /*для вывода данных на экран*/

fail, write_lines.

Пример 2. Вывести данные файла на экран.

Программа 28. Чтение данныхиз файла

Domains

str = string

file = datafile

Predicates

read_write_lines

Goal

openread(datafile,"file1.dat"),

read_write_lines,

closefile(datafile).

Clauses

read_write_lines :-

readdevice(datafile),

not(eof(datafile)),

readln(Line),

writedevice(screen),

write(" ",Line),nl,

read_write_lines.

Пример 3. Записать в файл данные, вводимые с клавиатуры

Программа 29. Запись в файл данных, вводимых с клавиатуры

Domains

file = datafile

dstring, cstring = string

Predicates

readin(dstring,cstring)

create_a_file

Goal

create_a_file.

Clauses

create_a_file :-

nl,nl,

write("Пожалуйста, введите полное имя файла."),

nl,nl,

readln(Filename), openwrite(datafile,Filename),

writedevice(datafile),

readln(Dstr),

concat(Dstr,"\13\10",Cstr),

readin(Dstr,Cstr),

closefile(datafile).

readin("done",_) :- !.

/*ввод данных завершится после вода слова "done"*/

readin(_,Cstr) :-

write(Cstr),

readln(Dstrl),

concat(Dstrl, "\13\10",Cstr1),

writedevice(datafile),

readin(Dstrl,Cstr1).

Предикаты для работы с файлами прямого доступа

Openmodify(fn,filename)-связывает логическое имя файла fn с именем файла

Filepos(fn, pos, mode)-устанавливает указатель файла в заданную позицию

Таблица 12.

Действие системы при операциях с файлами прямого доступа

Режим mode	Действия системы
0	Смещение берется относительно начала файла
1	Смещение берется относительно текущей позиции
2	Смещение берется относительно конца файла

Пример 4. Данные, вводимые с клавиатуры, записать в файл прямого доступа.

Программа 30. Запись данных в файл прямого доступа

Domains

file = datafile

Predicates

create_a_random_access_file

write_read_more(real, string)

pad_str (strIng,string,integer)

Goal

create_a_random_access_file.

Clauses

create_a_random_access_file :-

write("Please enter filename:"),nl,

readln(Filename),

openwrite(datafile,Filename),

closefile(datafile),

openmodify(datafile,Filename),

write("Введите строку"),nl,

readln(Dstr),

write_read_more(0,Dstr),

closefile(datafile).

write_read_more(_,"done") :-

nl, write(" Press the space bar."),

readchar(_),exit.

write_read_more(Index,Dstr) :-

writedevice(datafile),

filepos(datafile,Index,0),

pad_str(Dstr,Padstr,38),

concat(Padstr, "\10\13", Cstr),

write(Cstr),

writedevice(screen),

write("Введите строку"),nl,

readln(Dstr1),

Index1 = Index + 40,

write_read_more (Index1, Dstr1).

pad_str (Instr,Instr,Length) :-

str_len(Instr,Testlength),

Testlength >= Length,!.

pad_str (Instr,Padstr,Length) :-

concat(Instr,"-",Newstr),

pad_str(Newstr,Padstr,Length).

Пример 5. Вывести на экран заданную строку файла прямого доступа и выдача их на экран

Программа 31. Вывод данных из файла прямого доступа

Domains

file = datafile

Predicates

read_a_random_access_file

Goal

read_a_random_access_file.

Clauses

read_a_random_access_file:-

write("Please enter filename:"), nl, readln(Filename),

openread(datafile,Filename),

write("Type 1n record number: "),nl,

readreal(Record),

Index = (Record - 1) * 40,

readdevice(datafile),

filepos(datafile,Index,0),

readln(Cstr),

write(Cstr), nl,nl,

write("Press the space bar."),nl,

readdevice(keyboard),

readchar(_),

closefile(datafile),

exit.

Задание для самостоятельной работы

1) В файле задана последовательность целых чисел, найти сумму чисел, предшествующих первому отрицательному.

2) Переписать данные файла в обратном порядке.

3) Вывести на экран данные файла в неубывающем порядке.

4) Записать результат сложения чисел, содержащихся в файлах в третий.

5) Переписать числа из файла в другой, дописав за каждым его квадрат.

Лабораторная работа №8. Создание динамической базы данных. Предикаты для работы с базой данных

Для описания предикатов динамической базой данных предназначен раздел database. База данных (БД) называется динамической потому, что во время работы можно добавлять, удалять содержащиеся в них утверждения. Другая важная особенность динамических баз данных состоит в том, что она может быть записана на диск и считана с диска в оперативную память.

Иногда предпочтительно иметь часть информации БД в виде утверждений статической БД. Эти данные заносятся в динамическую сразу после активизации программы. В общем случае, предикаты статической БД имеют другое имя, но ту же самую форму представления данных, что и предикаты динамической.

Предикаты для работы с динамической БД:

Asserta заносит новый факт в БД, новый факт помещается перед всеми уже внесенными утверждениями.

Assertz помещает новый факт в БД за всеми имеющимися утверждениями.

Retract удаляет утверждение из БД.

Save сохраняет находящуюся в оперативной памяти БД в текстовом файле. Синтаксис этого предиката таков Save(DOS_file_name)

consult (DOS_file_name) считывает в память файл БД

readterm(Domain,Term) используется для чтения из файла объектов, относящихся к определенному в программе домену.

Предикат findall позволяет собрать все имеющиеся в базе данные в список, который может быть полезен при дальнейшей работе.

В качестве примера рассмотрим БД по игрокам футбольных команд, БД допускает следующие операции: добавление, удаление и просмотр данных. Эта программа создает БД и содержит её в оперативной памяти. Для работы с ней использовался предикат player с аргументами p_name-имя игрока, k_name-название клуба, p_number-номер игрока, pos-позиция игрока, height -рост, weight-вес, nfl_exp-стаж выступлений, college-учебное заведение)

Программа 32. Динамическая база данных «Футбольная команда»

Domains

p_name,k_name, pos, college = string

p_number, height, weight, nfl_exp = integer

Database

dplayer(p_name, k_name,p_number,pos, height,weight,nfl_exp, college)

Predicates

repeat

do_mbase

assert_database

process(integer)

clear_database

player(p_name, k_name,p_number,pos, height,weight,nfl_exp, college)

error

Goal

do_mbase.

Clauses

repeat.

repeat:-repeat.

/*База данных футбол*/

player("Иванов Иван","Спартак",13,"з", 205,90,3, "ГГПИ").

player("Петров Петр","Динамо",96,"пз", 185,78,4, "ГТК").

player("Сидоров Денис","Локомотив",69,"в", 190,88,2, "ГТУ").

player("Васечкин Илья","Торпедо",5,"в", 195,80,5, "ГГПИ").

player("Алексеев Дима","ЦСКА",1,"н", 165,67,2, "ГТК").

player("Карпов Павел","Зенит",12,"н",170,74,1, "ГКК").

/*конец начальных данных*/

assert_database:-

player(P_name,K_name,P_number,Pos,Height,Weight,Nfl_exp,College), assertz(dplayer(P_name,K_name,P_number,Pos,Height,Weight,Nfl_exp,

College)),

fail.

assert_database:-!.

clear_database:-

retract(dplayer(_,_,_,_,_,_,_,_)),

fail.

clear_database:-!.

do_mbase :-

assert_database,

makewindow(1,7,7," FOOTBALL DATABASE ",0,0,25,80),

menu,

clear_database.

menu :-

repeat, clearwindow,

nl,

write(" ************************************* "),nl,

write(" * 1. Добавление нового игрока в БД * "),nl,

write(" * 2. Удаление игрока из БД * "),nl,

write(" * 3. Просмотр данных * "),nl,

write(" * 4. Выход из программы * "),nl,

write(" ************************************* "),nl,

write(" Пожалуйста, сделайте свой выбор 1, 2, 3 or 4 : "),

readint(Vibor),nl,process(Vibor),Vibor = 4,!.

/* Добавление информации об игроке в БД */

process(1) :-

makewindow(2,7,7,"Добавление данных",2,20,18,58),shiftwindow(2),

write("Введите, пожалуйста:"),nl,

write("Имя игрока: "), readln(P_name),

write("Название клуба: "), readln(K_name),

write("Номер игрока: "), readint(P_num),

write("Позицию: "), readln(Pos),

write("Рост: "), readint(Ht),

write("Вес: "), readint(Wt),

write("Стаж выступлений: "), readint(Exp),

write("Название учебного заведения: "), readln(College),

assertz(dplayer(P_name, K_name, P_num,Pos,Ht,Wt,Exp, College)),

write(P_name," добавлен в БД"), nl,!,

write("Press space bar. "), readchar(_),

removewindow, shiftwindow(1).

/* Удаление */

process(2) :-

makewindow(3,7,7,"Удаление данных",10,30,7,40),shiftwindow(3),

write("Введите имя удаляемого игрока: "), readln(P_name),

retract(dplayer(P_name,_,_,_,_,_,_,_)),

write(P_name," удален из БД "), nl, !,

write("Press space bar."), readchar(_), removewindow,

shiftwindow(1).

/* Просмотр данных об игроке*/

process(3) :-

makewindow(4,7,7," Просмотр ", 7,30,16,47), shiftwindow(4),

write("Введите имя для просмотра: "), readln(P_name),

dplayer(P_name,T_name,P_number,Pos,Ht,Wt,Exp,College),nl,

write(" Имя игрока : ",P_name),nl,

write(" Название клуба : ",T_name),nl,

write(" Номер игрока : ",P_number),nl,

write(" Позиция : ",Pos),nl,

write(" Рост : ",Ht), nl,

write(" Вес : ",Wt),nl,

write(" Стаж выступлений : ",Exp), nl,

write(" Учебное заведение : ",College),nl, nl,!,

write("Press space bar"), readchar(_),

removewindow, shiftwindow(1).

process(3) :-

makewindow(5,7,7," Неудача ",14,7,5,60), shiftwindow(5),

write("К сожалению, данных нет."),nl,

write("Извините, пока!"),nl,!,

write("Press space bar."),readchar(_),

removewindow,shiftwindow(1).

/* Выход */

process(4) :-

write("До новых встреч! "),readchar(_),exit.

/*Обработка ошибки*/

process(Vibor):-

Vibor<1, error; Vibor>5, error.

error:-

write("Пожалуйста выберите число от 1 до 4"),

write("(Press the spase bar to continue)"),readchar(_).

Задание для самостоятельной работы

Модифицируйте программу, добавив в меню пункты:

1) Вывод списка игроков.

2) Сохранение данных в файл.

3) Выборка данных по 1 из трех критериев.

Тема: Получение структурированной информации из базы данных.

Задание.

1. Создать базу данных о заданной предметной области в виде множества фактов языка Пролог (не менее 5 фактов). Информацию о каждом компоненте БД представить в виде структуры.

2. Разработать набор предикатов, осуществляющих взаимодействие с БД, при помощи которых можно реализовать все типы запросов, приведенные в варианте задания. Найденные решения записать в виде фактов внутренней базы данных Пролога.

3. Предусмотреть проверку факта, являющегося ответом на запрос в БД. Если такой факт существует, то выдать его в качестве ответа на запрос. Если такого факта не существует в базе данных, то запустить запрос на выполнение и записать результат в БД.

Вариант №1.

Предметная область – семья. Каждая семья может быть описана структурой из трех компонент: мужа, жены и детей. Каждый член семьи может быть описан структурой: имя, отчество, фамилия, год рождения, пол, ежемесячный доход. Для детей добавить поле «близнец».

Реализовать следующие типы запросов:

1. Проверить, существует ли в БД заданный человек (по ФИО);

2. Найти всех работающих детей;

3. Найти всех работающих мужей, чей доход больше чем у жены;

4. Найти всех людей, которые не работают и родились до указанного года;

5. Найти число семей, у которых есть близнецы.

Вариант №2.

Реализовать следующие типы запросов:

1. Найти всех близнецов;

2. Найти всех детей, родившихся в заданном году;

3. Найти всех работающих жен, чей доход больше заданной суммы;

4. Найти фамилии людей, у которых есть заданное число детей.

5. Найти самого старшего ребенка в БД.

Вариант №3.

Реализовать следующие типы запросов:

1. Найти всех людей, чей доход меньше заданного;

2. Найти всех детей, младше заданного возраста;

3. Найти всех неработающих жен, которые родились позже заданного года;

4. Найти всех детей, у которых разница в возрасте родителей превышает заданную величину;

5. Подсчитать количество семей, у которых нет близнецов.

Вариант №4.

Предметная область – библиотека. Каждая книга может быть описана структурой: название, автор, список изданий, число экземпляров. Автор может быть описан структурой: имя, фамилия, год рождения. Издание может быть описано структурой: издательство, номер издания, год издания, количество страниц, цена.

Реализовать следующие типы запросов:

1. Найти автора, у которого книга имеет самый ранний год издания;

2. Найти все книги, изданные более одного раза (проверка по номеру издания);

3. Найти все книги, изданные в заданном издательстве за последние десять лет;

4. Найти все книги заданного автора;

5. Найти все книги, цена которых превышает заданную сумму.

Вариант №5.

Реализовать следующие типы запросов:

1. Найти книгу, у которой минимальная цена;

2. Найти все книги, изданные только один раз (проверка по номеру издания);

3. Найти всех авторов, родившихся позже указанного года;

4. Найти все издательства, в которых была издана указанная книга;

5. Найти все книги, количество страниц в которых не превышает заданного значения.

Вариант №6.

Реализовать следующие типы запросов:

1. Найти книгу, у которой максимальное число страниц;

2. Найти все книги, изданные в заданном издательстве;

3. Найти всех авторов, книги которых имеют цену, находящуюся в заданном диапазоне;

4. Найти все книги, которые имеются в нескольких экземплярах;

5. Найти все издательства, выпускавшие книги после указанного года.

Вариант №7.

Предметная область – страны мира. Каждая страна может быть описана структурой: название, площадь, географическое положение, население. Географическое положение может быть описана структурой: часть света, материк, океаны, моря, горные хребты. Население может быть описано структурой: численность, государственный язык, национальный состав. Национальный состав может быть описан структурой: национальность, численность, процент от всего населения.

Реализовать следующие типы запросов:

1. Найти страну, у которой максимальная численность населения;

2. Найти все страны, находящиеся на указанном материке с населением больше заданной величины;

3. Найти все страны, у которых однородный национальный состав (численность основной национальности более 90%);

4. Найти все страны, имеющие выход к указанному морю;

5. Найти все страны с указанным государственным языком.

Вариант №8.

Реализовать следующие типы запросов:

1. Найти страну, которую омывает больше всего морей;

2. Найти все страны, на территории которых находится указанный горный хребет;

3. Найти все страны, у которых число национальностей превышает заданную величину;

4. Найти все горные хребты, находящиеся на территории указанной страны;

5. Найти все страны, у которых численность населения меньше заданной величины.

Вариант №9.

Реализовать следующие типы запросов:

1. Найти страну, у которой максимальная плотность населения;

2. Найти все моря, которые омывают территорию указанной страны;

3. Найти страну, у которой численность ни одной из национальностей не превышает 50%;

4. Найти все страны, имеющие выход к указанному океану;

5. Найти все страны, у которых название части света совпадает с названием материка.

Вариант №10.

Предметная область – биржа труда. Каждая вакансия может быть описана структурой: название предприятия, должность, ежемесячный доход, требования к соискателю, список соискателей. Каждый соискатель может быть описан структурой: фамилия, имя отчество, соответствие требованиям. Требования к соискателю и соответствие требованиям могут быть описаны одной структурой: образование, возраст, пол, владение иностранными языками, умение работать на ПК, стаж работы по специальности.

Реализовать следующие типы запросов:

1. Найти должность, для которой существует максимальное число соискателей;

2. Найти все должности для мужчин, с высшим образованием и свободно владеющих иностранным языком;

3. Найти все предприятия, предлагающие доход выше указанного уровня;

4. Найти всех соискателей, умеющих работать на ПК, и имеющих стаж работы более 5 лет;

5. Найти предприятия, у которых есть заданная вакансия.

Вариант №11.

Реализовать следующие типы запросов:

1. Найти всех соискателей, которые соответствуют требованиям по заданной должности;

2. Подсчитать количество соискателей, имеющих высшее образование;

3. Найти все должности для соискателей, указанной специальности;

4. Найти все должности для мужчин с ежемесячным доходом выше указанного значения;

5. Найти все должности, для которых не требуется высшего образования.

Вариант №12.

Реализовать следующие типы запросов:

1. Найти должность, у которой минимальный ежемесячный доход;

2. Найти все должности для мужчин, с указанным уровнем образования, владеющих хотя бы одним иностранным языком;

3. Найти предприятия, для вакансий которых нет соискателей;

4. Найти все должности для женщин, не старше указанного возраста;

5. Найти все должности, для которых требуется знание иностранного языка.

Вариант №13.

Предметная область – служба знакомств. Каждый клиент может быть описан структурой: фамилия, имя, отчество, характеристика клиента, требования к партнеру, список возможных партнеров. Характеристика клиента и требования к партнеру могут быть описаны одной структурой: возраст, образование, национальность, ежемесячный доход, владение жилой площадью, наличие детей, отсутствие вредных привычек. Возможный партнер может быть описан следующей структурой: фамилия, имя, отчество, характеристика партнера. Характеристика партнера может быть описана структурой, одинаковой со структурой характеристики клиента.

Реализовать следующие типы запросов:

1. Подсчитать количество клиентов в БД;

2. Найти всех клиентов, с указанным уровнем образования, имеющих жилую площадь, без вредных привычек;

3. Найти всех возможных партнеров с указанной национальностью;

4. Найти всех клиентов, которым необходим партнер, не старше указанного возраста и не имеющий детей;

5. Найти клиента, которому требуется самый молодой партнер.

Вариант №14.

Реализовать следующие типы запросов:

1. Найти всех клиентов, для которых требования к партнеру совпадают с характеристикой партнера;

2. Найти всех партнеров указанного клиента, у которых есть дети;

3. Найти всех клиентов с заданным уровнем дохода и младше указанного возраста;

4. Найти самого старого клиента службы знакомств;

5. Найти всех клиентов, у которых нет жилой площади и есть вредные привычки.

Вариант №15.

Реализовать следующие типы запросов:

1. Найти самого молодого возможного партнера в БД;

2. Найти клиента, у которого нет возможных партнеров;

3. Найти всех клиентов указанной национальности, не старше указанного возраста;

4. Найти всех партнеров указанного клиента без вредных привычек;

5. Найти всех клиентов, у которых нет детей, и которым подходит партнер, имеющий детей.

Вариант №16.

Предметная область – спортивные соревнования. Каждое соревнование может быть описано структурой: ранг соревнований, вид спорта, год проведения, страна проведения, список команд - участников. Команды - участники могут быть описаны следующей структурой: название команды, страна, результаты соревнований. Результаты соревнований могут быть описаны списком структур: название команды – соперника, страна, тип результата (выигрыш, проигрыш, ничья).

Реализовать следующие типы запросов:

1. Найти ранг соревнования, в котором участвовало минимальное число команд, в заданном году и в заданном виде спорта;

2. Найти все команды указанного ранга соревнований и года проведения, у которых не было ни одного проигрыша;

3. Найти всех соперников указанной команды в соревнованиях заданного ранга в заданном году;

4. Найти вид спорта, в котором проводились соревнования в заданном году;

5. Найти все команды указанной страны, участвовавшие в соревнованиях заданного ранга.

Вариант №17.

Реализовать следующие типы запросов:

1. Найти вид спорта, в котором участвовало максимальное число команд, в заданном году и в заданном ранге соревнований;

2. Найти все страны, где проводились чемпионаты мира по указанному виду спорта.

3. Найти всех соперников указанной команды в соревнованиях определенного ранга в заданном году;

4. Найти все соревнования, проводившиеся в заданном году;

5. Найти все команды, у которых были ничьи.

Вариант №18.

Реализовать следующие типы запросов:

1. Найти год, в который участвовало максимальное число команд, в заданном виде спорта и в заданном ранге соревнований;

2. Найти вид спорта, в котором выступает заданная команда;

3. Найти все команды, которые участвовали в Олимпийских играх по определенному виду спорта;

4. Найти все команды, участвовавшие в соревнованиях в заданном году;

5. Найти все команды определенной страны, у которых были выигрыши.

Вариант №19.

Предметная область – видеотека. Каждая видеокассета может быть описана структурой: название фильма, год создания, киностудия, атрибуты фильма. Атрибуты фильма могут быть описаны структурой: автор сценария, режиссер, список фамилий исполнителей главных ролей, премии. Премии могут быть описаны списком из следующих структур: название фестиваля, год проведения.

Реализовать следующие типы запросов:

1. Найти фильм, получивший больше всего премий;

2. Подсчитать число фильмов указанного режиссера;

3. Найти всех режиссеров, фильмы которых создавались на заданной киностудии;

4. Найти все фильмы, определенного актера за указанный период времени;

5. Найти всех сценаристов, в фильмах которых снимался определенный актер.

Вариант №20.

Реализовать следующие типы запросов:

1. Найти сценариста, в фильме которого снялось минимальное число актеров;

2. Найти режиссеров и сценаристов, у которых есть фильмы, получившие премии;

3. Найти все фильмы указанного режиссера, снятого на определенной киностудии;

4. Найти всех исполнителей главных ролей указанного фильма;

5. Найти все киностудии, которые работали с указанным режиссером.

Вариант №21.

Реализовать следующие типы запросов:

1. Найти режиссера, у которого фильм получил максимальное число премий;

2. Найти все фильмы, получившие премии, в которых снимался указанный актер;

3. Найти все фильмы определенного сценариста, снятые в указанном году.

4. Найти количество актеров, снимавшихся на определенной киностудии;

5. Найти всех актеров, снимавшихся в фильмах определенного сценариста.

Вариант №22.

Предметная область – учебная группа факультета. Каждая учебная группа может быть описана структурой: название факультета, код специальности, номер группы, состав группы. Состав группы может быть описан списком структур, описывающих отдельного студента: фамилия, имя, отчество, обучение на военной кафедре, сводная ведомость. Сводная ведомость может быть описана списком из следующих структур: предмет, оценка.

Реализовать следующие типы запросов:

1. Подсчитать число групп определенной специальности;

2. Найти оценку определенного студента по заданному предмету;

3. Найти группу, которая сдала больше всего предметов в сессию;

4. Найти всех студентов, имеющих задолженности;

5. Подсчитать число студентов, обучающихся на военной кафедре.

Вариант №23.

Реализовать следующие типы запросов:

1. Подсчитать общее число студентов на указанном факультете;

2. Найти группу, у которой больше всего отличников;

3. Найти все предметы, которые изучала определенная группа;

4. Найти всех студентов, не обучающихся на военной кафедре;

5. Найти все группы, изучавшие определенный предмет.

Вариант №24.

Реализовать следующие типы запросов:

1. Подсчитать средний балл сессии по указанной группе;

2. Найти группу, в которой минимальное число студентов;

3. Найти все предметы в указанной группе, по которым сдавался экзамен;

4. Найти код специальности указанной группы;

5. Найти всех студентов, обучающихся на военной кафедре.

Вариант №25.

Предметная область – база данных продажи автомобилей. Каждый автомобиль может быть описана структурой: марка автомобиля, страна фирмы-изготовителя, список фирм-продавцов. Фирма-продавец может быть описана структурой: название фирмы, страна, список имеющихся моделей. Модель может быть описана структурой: наименование модели, цена, список имеющихся расцветок.

Реализовать следующие типы запросов:

1. Найти марку автомобиля, которую продает больше всего фирм;

2. Подсчитать число стран, в которых продаются автомобили заданной марки;

3. Найти все фирмы, продающие автомобили заданной марки;

4. Найти все модели автомобилей, цена которых ниже заданной;

5. Найти все фирмы, которые продают автомобили заданной модели.

Вариант №26.

Реализовать следующие типы запросов:

1. Найти марку и модель автомобиля, у которой минимальная цена;

2. Подсчитать число расцветок автомобиля заданной модели у определенного продавца;

3. Найти все страны-изготовителя, выпускающие автомобили заданной марки;

4. Найти все марки автомобилей, продающиеся в заданной стране;

5. Найти все фирмы, которые продают автомобили заданной расцветки.

Вариант №27.

Реализовать следующие типы запросов:

1. Найти марку и модель автомобиля, у которой максимальное число расцветок;

2. Подсчитать число фирм, в которых продаются автомобили заданной марки;

3. Найти все фирмы, продающие автомобили в заданной стране;

4. Найти все марки автомобилей, выпускающиеся в заданной стране;

5. Найти все фирмы, которые продают автомобили заданной цены.

Вариант №28.

Предметная область – расписание движения самолетов. Каждый рейс может быть описан структурой: название авиакомпании, номер рейса, пункт отлета, пункт прилета, время отлета, время прилета, список пунктов промежуточных посадок, список тарифов. Тариф может быть описан структурой: тип класса салона, цена.

Реализовать следующие типы запросов:

1. Найти авиакомпанию, у которой максимальная стоимость билета по заданному маршруту;

2. Подсчитать число авиакомпаний, самолеты которых летают в заданный город (включая промежуточные посадки);

3. Найти все номера рейсов, улетающих до указанного времени;

4. Найти все авиакомпании, самолеты которых летают из указанного города;

5. Найти все рейсы, на которые есть билеты эконом класса.

Вариант №29.

Реализовать следующие типы запросов:

1. Найти авиакомпанию, у которой минимальная продолжительность полета по заданному маршруту;

2. Подсчитать число рейсов, совершающих промежуточную посадку в заданном пункте;

3. Найти все авиакомпании, у которых есть билеты бизнес класса;

4. Найти все рейсы, прилетающие в указанный пункт до заданного времени;

5. Найти все рейсы, летающие по заданному маршруту.

Вариант №30.

Реализовать следующие типы запросов:

1. Найти авиакомпанию, у которой максимальное число тарифов на заданный маршрут;

2. Подсчитать число рейсов, улетающих из заданного города до указанного времени;

3. Найти все авиакомпании, у которых есть билеты класса люкс;

4. Найти все рейсы, у которых цена билета ниже заданной;

5. Найти все авиакомпании, у которых время полета меньше заданного.

Лабораторная работа №9. Применение языка для решения задач ИИ. Создание экспертных систем

Пример 1.Рассмотрим пример ЭС для идентификации породы собак. Она помогает потенциальному хозяину выбрать породу собаки в соответствие с определенными критериями.

В данной ЭС используются следующие характеристики:

1. Короткая шерсть;

2. Длинная шерсть;

3. Рост меньше 30 дюймов;

4. Рост меньше 22 дюймов;

5. Низкопосаженный хвост;

6. Длинные уши;

7. Хороший характер

8. Вес больше 100 фунтов.

Каждая характеристика для конкретной породы либо верна, либо не верна. Для каждой породы справедливы следующие характеристики:

Таблица 13.

Характеристики собак

Порода	Характеристики
Английский бульдог	1,4,5,7
Гончая	1,4,6,7
Дог	1,3,6,7,8
Амер.гончая	1,5,6,7
Кокер-спаниэль	2,4,5,6,7
Ирландский сеттер	2,3,6
Колли	2,3,5,7
Сенбернар	2,5,7,8

Программа 33. «Эксперт по породам собак»

*Эксперт по породам собак*/

/*Назначение: Демонстрация работы ЭС*/

Domains

n=integer

list=n*

dog=symbol

Predicates

rule(n,dog,list)

cond(n,string)

do_expert

show_menu

do_consulting

process(n)

test(n,list)

topic

repeat

Goal

do_expert.

Clauses

rule(1,"английский бульдог",[1,4,5,7]).

rule(2,"гончая",[1,4,6,7]).

rule(3,"дог",[1,3,6,7,8]).

rule(4,"американская гончая",[1,5,6,7]).

rule(5,"коккер-спаниель",[2,4,5,6,7]).

rule(6,"ирландский сеттер",[2,3,6]).

rule(7,"колли",[2,3,5,7]).

rule(8,"сенбернар",[2,5,7,8]).

/*Характеристики*/

cond(1,"короткошерстная").

cond(2,"длинношерстная").

cond(3,"рост ниже 30 дюймов").

cond(4,"рост ниже 22 дюймов").

cond(5,"низкопосаженный хвост").

cond(6,"большие уши").

cond(7,"хороший характер").

cond(8,"вес более 100 фунтов").

do_expert:-

makewindow(1,7,5 ,"ЭКСПЕРТНАЯ СИСТЕМА",0,0,25,80),

show_menu.

repeat.

repeat:-repeat.

/*Вывод меню*/

show_menu:-

repeat,

write("***************************"),nl,

write("*****Добро пожаловать!*****"),nl,

write("* *"),nl,

write("*****1-консультация********"),nl,

write("*****2-список**************"),nl,

write("*****3-выход***************"),nl,

write("* *"),nl,

write("****Сделайте свой выбор****"),nl,

readint(X),

process(X),fail.

/*Обработка 1 пункта меню “Консультация”*/

process(1):-

do_consulting,

readchar(_),

shiftwindow(1),

clearwindow.

/*Обработка 2 пункта меню “Вывод списка”*/

process(2):-

makewindow(2,7,7,"",5,20,12,25),

topic,

readchar(_),

shiftwindow(1),

clearwindow.

/* Обработка 3 пункта меню “Выход”*/

process(3):-

removewindow,

exit.

/*Вывод пород собак*/

topic:-

rule(X,Y,_),

write(X,". ",Y),

nl,fail.

topic.

/*Консультация*/

do_consulting:-

test(1,List),

rule(_,X,List),

write("Ваш выбор:" ,X),!.

do_consulting:-

write("Мне жаль, что не смог Вам помочь.").

/*Тестирование*/

test(9,[]):-!.

test(1,[N|List]):-

cond(N,Text),

makewindow(2,7,7,"",5,20,10,35),

write("Вопрос:-",Text,"?"),nl,

write("1-да"),nl,

write("0-нет"),nl,

readint(R),R=1,!,test(3,List).

test(1,List):- test(2,List),!.

test(N,[N|List]):-

cond(N,Text),

makewindow(2,7,7,"",5,20,10,35),

write("Вопрос:-",Text,"?"),nl,

write("1-да"), nl,

write("0-нет"), nl,

readint(R),M=N+1,

R=1,!,test(M,List).

test(N,List):-M=N+1,test(M,List).

Задания для самостоятельной работы

Разработать экспертную систему, тему выбрать самостоятельно. Отчет должен содержать следующие пункты:

1. Тема ЭС.

2. Назначение, возможности программы.

3. Разработать структурно-функциональную схему.

4. Определить базу знаний, разработать механизм вывода, интерфейс программы.

5. По каким параметрам программу можно отнести к классу ЭС.

Рекомендуемая литература

1. Братко И. Программирование на языке Пролог для ИИ: Пер. с англ.- М.- Мир, 1990

2. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

3. Марселлус Д. Программирование экспертных систем на ТурбоПрологе: Пер. с англ./Предисл. С.В.Трубицына.-М.-Финансы и статистика, 1994.-256с.:ил.

4. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер.с англ.-М.: Мир, 1990.-235 с., ил.

5. Таунсенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ: Пер. с англ./Предисл. Г.С.Осипова.-М. .-Финансы и статистика, 1990.-320с.:ил.

Литература

1. Братко И. Программирование на языке Пролог для ИИ: Пер. с англ.- М.- Мир, 1990

2. Доорс Дж., Рейблейн А.Р., Вадера С. Пролог-язык программирования будущего: Пер. с англ.- М.- Финансы и статистика, 1990

3. Стобо Д.Ж. Язык программирования Пролог: Пер. с англ.- М.- Радио и связь, 1993.-368 с.:ил.

4. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

5. Информатика. Задачник-практикум в 2 т./Под ред. И.Г.Семакина, Е.К. Хеннера: Том.2.-М.:-БИНОМ. Лаборатория знаний, 2003.-278 с.:ил.

6. Информатика:Учеб.пособие для студ.пед.вузов/А.В.Могилев, Н.И.Пак, Е.К.Хеннер;Под ред. Е.К.Хеннера.-3-е изд., перераб. и доп.-М.:Издательский центр “Академия”, 2004.-848 с.

7. Каймин В.А. Основы компьютерной технологии.- М.:Финансы и статистика, 1992.-208 с.: ил.

8. Каймин В.А. Информатика: Учебник.-2-е изд., перераб. и доп.-М.-ИНФРА-М,2001.-272 с.

9. Кларк К., Маккей Ф. Введение в логическое программирование на микро-Прологе. Пер. с англ.- М.- Радио и связь, 1987.

10. Клоксин У., Меллиш К. Программирование на языке Пролог: Пер.с англ.-М.: Мир, 1987.

11. Малпас Дж. Реляционный язык Пролог и его применение. Пер. с англ./Под ред. В.Н. Соболева.-М.-Наука, 1990

12. Марселлус Д. Программирование экспертных систем на ТурбоПрологе: Пер. с англ./Предисл. С.В.Трубицына.-М.-Финансы и статистика, 1994.-256с.:ил.

13. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер.с англ.-М.: Мир, 1990.-235 с., ил.

14. Таунсенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ: Пер. с англ./Предисл. Г.С.Осипова.-М. .-Финансы и статистика, 1990.-320с.:ил.

15. Хоггер К. Введение в логическое программирование: Пер. с англ.-М.: Мир, 1988.-348 с.

Глоссарий

Анонимная переменная

переменная с именем "_". Считается, что все анонимные переменные являются некоторыми уникальными, однократно использованными именами.

Арность

количество аргументов предиката.

Головная цель предложения

см. Заголовок предложения.

Декларативный язык программирования (от лат. Declaratio - объявление)

язык программирования высокого уровня, построенный на описании данных и на описании искомого результата. Декларативные языки подразделяются на функциональные и логические языки.

Детерминированная (Недетерминированная) цель

такая цель, в результате доказательства которой не возникают (возникают) новые точки возврата.

Домен (тип данных)

характеристика набора данных, которая определяет диапазон возможных значений данных из набора, допустимые операции, которые можно выполнять над этими значениями, способ хранения этих значений в памяти. Различают простые типы данных: целые, действительные числа и др., составные типы данных: структуры, списки и др.

Заголовок предложения

атомарная формула в начале предложения, стоящая перед разделителем ":-".

Лексема

наименование смысловой единицы, распознаваемой лексическим анализатором в тексте программы. Лексемами являются: переменные, символы и ключевые слова, целые числовые литералы, вещественные числовые литералы, сегменты строк, ограничители.

Логический язык программирования

язык программирования, позволяющий выполнить описание проблемы в терминах фактов и логических формул, а собственно решение проблемы выполняет система с помощью механизма логического вывода.

Логическое программирование

программирование в терминах фактов и правил вывода, с использованием языка, основанного на формальных исчислениях.

Поиск с возвратом (backtracking)

возобновление исполнения процесса доказательства целей, начиная с последней (неустранённой предикатом отсечения) точки возврата. В результате отката осуществляется отмена всех связываний и сцеплений переменных, произошедших в целях с момента прохождения точки возврата.

Правило вывода

правило, определяющее переход от посылок к следствиям. Правило вывода указывает, каким образом высказывания, истинность которых известна, могут быть видоизменены, чтобы получить новые истинные высказывания.

Предикат

синтаксическая конструкция, состоящая из предикатного имени и последовательности (возможно, пустой) аргументов. Предикат - свойство объекта или отношение между объектами, аргументами которого могут быть произвольные объекты из некоторого множества, а значениями предиката могут быть "истина" или "ложь".

Предикат отсечения ("!", cut)

стандартный предикат, устраняющий все неисследованные пути (нерассмотренные точки возврата), которые встретились с момента начала исполнения предиката, в соответствие которому было поставлено предложение, содержащее предикат.

Предложение

логическое правило, состоящее из заголовка и последовательности (возможно, пустой) подцелей.

Рекурсивный тип данных

тип данных, допускающий структуры, содержащие структуры, как и он сами.

Список

упорядоченная последовательность элементов данных, каждый из которых может быть либо списком, либо атомарным неделимым элементом.

Терм

синтаксическая конструкция, обозначающая элемент данных. Различаются простые термы и составные термы.

Точка возврата

неисследованный путь, по которому может пойти исполнение программы в случае отката.

Унификация

операция сравнения (отождествления) двух объектов, связывающая переменные в составе объектов. Унификация различных (несвязанных) переменных приводит к сцеплению этих переменных.

Факт

знание в форме утверждения, достоверность которого строго установлена.

Функтор

имя, которому приписана некоторая арность (число аргументов).

Функциональный язык программирования

язык программирования, позволяющий задавать программу в виде совокупности определений функций. В функциональных языках программирования функции обмениваются между собой данными без использования промежуточных переменных и присваиваний, циклы заменяются аппаратом рекурсивных функций.

Целевое утверждение

утверждение, с доказательства которого начинается исполнение программы.

Язык программирования Лисп (LISP - LISt Processing)

универсальный язык программирования высокого уровня. Язык Лисп относится к декларативным языкам функционального типа, предназначен для обработки символьных данных, представленных в виде списков, основой языка являются функции и рекурсивные построения.

Язык программирования Пролог (PROLOG - PROgramming in LOGic)

язык логического программирования, программа на котором состоит из логических утверждений, образующих базу данных и из правила вывода новых утверждений из известных.

	A	B	C	D	E	F	G
A	-	1	0	0	0	0	0
B	1	-	1	0	1	0	0
C	0	1	-	1	0	0	0
D	0	0	1	-	1	0	0
E	0	1	0	1	-	0	0
F	0	0	0	0	1	0	0
G	0	0	0	0	1	0	-

	A	B	C	D	E	F	G
A	-	1	0	0	0	0	0
B	1	-	1	0	1	0	0
C	0	1	-	1	0	0	0
D	0	0	1	-	1	0	0
E	0	1	0	1	-	0	0
F	0	0	0	0	1	0	0
G	0	0	0	0	1	0	-

	A	B	C	D	E	F	G
A	-	1	0	0	0	0	0
B	1	-	1	0	1	0	0
C	0	1	-	1	0	0	0
D	0	0	1	-	1	0	0
E	0	1	0	1	-	0	0
F	0	0	0	0	1	0	0
G	0	0	0	0	1	0	-